정렬 알고리즘 - 1

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는 것이며 정렬의 목적은 대게  탐색을 위해 또 이진 탐색이 가능한 데이터를 만들기 위해서 입니다. :)

 

사실 Timsort 알고리즘 (삽입정렬 + 병합정렬)이 Python, Java, Android, Google chrome, swift 등에서 표준 정렬 알고리즘으로 채택된 정렬 방법이지만

 

정렬 방법의 기초를 다지기 위해서 쓰는 글이니만큼 이번엔 8가지 기본정렬 방법,

그리고 그중 버블정렬, 단순 선택 정렬, 단순 삽입 정렬에 대해 먼저 공부하려 합니다.

 

1. 버블 정렬 

이웃한 두 원소의 대소 관계를 비교해 필요에 따라 교환하는 방법으로 단순 교환 정렬이라고도 합니다.

https://www.acmicpc.net/problem/23968

23968번: 알고리즘 수업 - 버블 정렬 1

import sys

n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
flag = True
for i in range(n):
    if flag:
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                k -= 1
                if k == 0:
                    flag = False
                    break
if k == 0:
    print(a[j], a[j + 1])
else:
    print(-1)

 

2. 단순 선택 정렬

가장 작은 원소부터 혹은 큰 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘입니다. 시간복잡도 O(n**2)

https://www.acmicpc.net/problem/23881

23881번: 알고리즘 수업 - 선택 정렬 1

import sys
n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
n = len(a)
flag = True
for i in range(n - 1):
    max = 0
    for j in range(n - i):
        if a[j] > a[max]:
            max = j
    if (n - 1 - i) != max:
        k -= 1
        if k == 0:
            break
        a[n - 1 - i], a[max] = a[max], a[n - 1 - i]
if k == 0:
    print(a[j], a[max])
else:
    print(-1)

 

3. 단순 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘 입니다. 단순 선택정렬과 비슷하지만 원소를 선택하지 않는다는 차이가 있습니다. 시간복잡도 O(n**2)

https://www.acmicpc.net/problem/24051

import sys
n, k = map(int, sys.stdin.readline().strip().split())
a = list(map(int, sys.stdin.readline().strip().split()))
n = len(a)
flag1 = False
for i in range(1, n):
    if k == 0:
        break
    j = i
    tmp = a[i]
    flag2 = False #대소관계가 정렬되어 있는지 확인
    while j > 0 and a[j - 1] > tmp:
        flag2 = True  #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우
        k -= 1  #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우 변화했기 때문에 k - 1
        a[j] = a[j - 1]
        if k == 0:
            flag1 = False
            break
        j -= 1
    if k == 0:
        break
    if flag2: #대소관계가 정렬되어 있는지 확인 했을 때 정렬 되어있지 않은 경우 재정렬한 k - 1
        k -= 1
    a[j] = tmp
if k == 0:
    print(a[j])
else:
    print(-1)