기본적인 정렬 알고리즘

def bubblesort(x, n):
    for last in range(n, 1, -1):
    	#check sorting
        changed = False 
        for i in range(0, last-1, 1):
            if x[i]>x[i+1]:
                temp = x[i+1]
                x[i+1] = x[i]
                x[i] = temp
                changed = True
        if changed == False:
            return x
    return x

1.  선택 정렬 (Selection Sort)

selectionSort(A[], n) 
{
	for last<-n downto 2 #1
    {
    	A[1...last] 중 가장 큰 수 A[k]를 찾는다; #2
        A[k] ↔ A[last]; #3
    }
}	

last는 고정되지 않은 배열에서 가장 마지막 부분을 의미한다. 즉 뒤에서부터 채워나가는데 #2처럼 고정되지 않은 배열에서 가장 큰 수를 찾은다음 #3처럼 그 수를 고정되지 않은 배열의 가장 마지막 부분인 A[last]에 넣는 것이다. 

아래는 직접 구현해본 코드이다. 

def SelectionSort(x):
    last = len(x)-1
    for n in range(last, 1, -1):
        max_ = x[n]
        loc = n
        for j in range(n):
            if max_<x[j]:
                max_ = x[j]
                loc = j
        temp = x[n]
        x[n] = max_
        x[loc] = temp
    return x

 

2. 버블 정렬(Bubble Sort)

버블정렬도 선택 정렬처럼 제일 큰원소를 제일 오른쪽으로 옮긴다. 아래는 이것의 알고리즘이다. 

선택 정렬은 고정되지 않은 배열중 가장 큰 것을 하나 골라서 한번 바꾼다면, 버블정렬은 고정되지 않은 정렬을 왼쪽 오른쪽 계속 바꾼다.

아래는 직접 구현해본 코드이다. 

def bubblesort(x, n):
    for last in range(n, 1, -1):
    	#check sorting
        changed = False
        for i in range(0, last-1, 1):
            if x[i]>x[i+1]:
                temp = x[i+1]
                x[i+1] = x[i]
                x[i] = temp
                changed = True
        if changed == False:
            return x
    return x

위에서 #부분을 추가하였는데 원래 코드대로라면 이미 정렬이 완료가 되었어도 계속 진행이 되는데 changing을 감지함으로서 더이상 교환이 발생하지 않으면 sorting을 종료해 좀더 빠르게 끝낼 수 있다.

 

3. 삽입 정렬(Insertion Sort)

위에 선택 정렬과 버블 정렬은 n개의 배열에서 시작해서 하나씩 줄여감에 반면 삽입정렬은 1개 짜리 배열에서부터 시작한다. 알고리즘은 아래와 같다. 

위의 그림처럼 배열을 하나씩 늘려가면서 그 배열의 알맞은 곳에 수를 추가하는 것이다. 아래는 직접 구현해본 코드이다. 

def insertionSort(A, n):
    for i in range(1, n, 1):
        choosen = A[i]
        #A[0...i-1] already sorted
        loc = i-1
        while loc>=0 and choosen<A[loc]:
            temp = A[loc]
            A[loc] = choosen
            A[loc + 1] = temp
            loc -= 1
            
    return A
        

선택과 버블 정렬은 O(n^2)의 시간복잡도를 가진다면 이 정렬은 약간다르다. 물론 최악의 경우 즉 A[i]가 A[0](맨앞)으로 들어가게 된다면 i번의 순환이 필요하게 되어서 O(n^2)을 가지게 된다. 하지만 운이 좋다면 A[i]가 이미 고정된 배열에 맨끝에 들어가게 되고 순환이 필요없어지게 되면 O(n)의 시간만 걸리게 된다. for문 안쪽의 while이 돌아갈 필요가 없어지기 때문이다.