정렬 알고리즘(버블정렬, 선택정렬, 퀵정렬, 삽입정렬, 병합정렬, 계수정렬)

 정렬 알고리즘은 내가 생각하기에 제일 간단한 알고리즘인데... 종류가 많아서 머릿 속에 빡하고 안 들어오는 느낌이어서 정리해본다.

---

버블정렬(Bouble Sort)

이해하기

4

3

2

5

1

 위와 같은 수열이 있다고 하자. 버블 정렬을 이해하는 데 있어 중요한 것은 버블 정렬을 할 때 수열 중 어떤 하나의 수는 정렬을 따로 할 필요가 없다는 것이다. 왜냐하면 다른 수들이 모두 정렬된 상태라면 자연히 그 숫자도 자리를 찾은 것이기 때문이다.

4

3

2

5(여기까지만)

1

 처음 4에서 시작해보자. 우리는 4라는 수를 꺼내서 5가 있는 네번째 자리까지만 가면 된다. 왜냐하면 앞수와 뒷수를 비교하는 과정에서 마지막으로 5와 1을 비교하게 될 것이고, 1은 수열의 마지막이라 비교할 뒷수가 없기 때문이다.

 4는 3과 비교해서 더 크므로 3과 자리가 바뀌고, 4와 2는 또 바뀌게 된다. 그리고 원래 2의 자리였던 array[2]를 차지하게 된 4는 5보다 작으므로 그 자리를 지키게 된다. 그리고 5는 1보다 크므로 1과 자리가 바뀐다. 그 결과 아래와 같다.

3

2

4

1

5

 이렇게 앞수를 하나 잡아서 비교하는 과정이 끝났다. 이후의 과정은 지금 해온 것과 같다. 다만 주의할 점은 우리가 이미 한 번의 정렬 과정을 거치면서 5의 자리를 확정지었다는 것이다. 그렇기 때문에 두번째 정렬 과정에 들어갈 때는 아까 네번째자리까지 진행했던 것과는 달리 한 자리 덜 진행하면 된다. 두번째 과정은 아래와 같다.

3

2

4(여기까지만)

1

5

 두번째 과정을 거치게 되면 아래와 같이 정렬된다.

2

3

1

4

5

 같은 방법으로 세번째 과정을 거치게 되면 아래와 같다.

2

1

3

4

5

 네번째 과정을 거치게 되면 아래와 같이 정렬이 끝난다.

1

2

3

4

5

코드로 나타내기

 

 버블정렬은 우리가 어떤 수열을 정렬시켜야 한다고 할 때, 가장 쉽게 떠올릴 수 있는 방법이다. 앞수와 뒷수를 비교해가며 크기에 따라 정렬시키는 방법. 이해하기에서 했던 방법으로 간단하게 정리해보면 이렇다.

 

1. 정렬을 하려면 (길이-1)번째 과정을 거쳐야 한다.

2. 정렬하는 과정을 거칠수록 정렬시켜야 하는 숫자의 갯수는 1개씩 줄어든다.

 

 이를 토대로 코드를 작성하면 아래와 같다.

# 오름차순

def boubleSort(list):
    if len(list)<=1:
        return list
    for i in range(len(list)-1):
        for j in range(len(list)-1-i): # 정렬시켜야 하는 숫자의 개수
            if list[j] > list[j+1]: # 앞수가 뒷수보다 크다면
                list[j], list[j+1]=list[j+1], list[j] # 자리를 바꿔준다.
    return list

시간복잡도는 O(N^2)이다.

---

선택정렬(Selection Sort)

이해하기

 선택정렬은 남아있는 수들 중 제일 작은 수를 앞으로 꺼내면서 정렬시키는 방법이다. 자세하게 말하자면 제일 작은 수를 찾아 그 당시 제일 앞에 있는 수와 자리를 바꾸어주는 것이다.

4

3

2

5

1

 위와 같은 수열이 있다고 하면 다섯개의 수들 중 가장 작은 1과 4의 위치를 바꾼다.

1(제외)

3

2

5

4

 그럼 위와 같이 수열이 바뀌고, 이미 정렬된 1을 제외하고 나머지 수들 중 제일 작은 2와 제일 앞에 있는 3을 바꿔준다.

1(제외)

2(제외)

3

5

4

 계속 위와 같은 과정을 거치게 된다.

1(제외)

2(제외)

3(제외)

5

4

1(제외)

2(제외)

3(제외)

4

5

 마침내 위처럼 정렬이 끝난다.

코드로 나타내기

def SelectionSort(numList):
    for i in range(len(numList)-1):
        min_index=i # 가장 작은 값의 위치를 나타낼 min_index. 수의 나열 중 가장 앞에 있는 수를 초기값으로 갖는다.
        for j in range(i+1, len(list)): # min_index 다음으로 나열된 수들 중 가장 작은 수를 찾는다.
            if numList[min_index]>list[j]: #제일 앞에 있는 수(numList[i])보다 뒤에 나열된 수들 중 작은 수가 있다면,
                min_index=j # min_index를 그 작은 수의 인덱스(j)로 바꿔준다.
        numList[i], numList[min_index]=numList[min_index], numList[i] # 그리고 새로 찾은 가장 작은 수와 가장 앞에 있던 수를 바꿔준다.
    return numList

시간복잡도는 O(N^2)이다.

---

퀵정렬(Quick Sort)

이해하기

 퀵정렬은 한 기준점(피봇, pivot)을 잡고 기준점보다 큰 값들과 작은 값들을 나눈 후 또다시 큰 값들 사이에서 피봇을 정해서 그 피봇보다 큰 값과 작은 값들을 나누고, 작은 값들 사이에서도 피봇을 정해서 또 정렬을 거쳐 최종적으로 정렬하는 방법이다.

 아래와 같이 제일 앞에 있는 수를 기준점으로 잡고 이 수를 기준으로 큰 값, 작은 값으로 나눈다.

4(피봇)

3

2

5

1

3

2

1

4(피봇)

5

 이제 왼쪽과 오른쪽 부분에서 각각 피봇을 정해서 정렬시킨다.

2

1

3(피봇)

 오른쪽부분은 5 하나밖에 없으므로 왼쪽 부분을 계속 정렬시켜 나간다.

1

2(피봇)

 

 이렇게 되면 왼쪽 부분의 정렬도 모두 끝나고, 정렬된 왼쪽부분과 피봇, 정렬된 오른쪽부분을 순서대로 합치면 정렬이 끝난다.

1

2

3

4

5

코드로 나타내기

 이해하기를 토대로 퀵 정렬의 포인트를 정리해보면 아래와 같다.

 

1. 숫자 하나를 기준으로 삼아서(피봇) 기준보다 큰 값과 기준보다 작은 값을 왼쪽, 오른쪽으로 나눈다.

2. 같은 방법으로 계속 부분을 쪼개어간다.

def quickSort(list):
    if len(list)<=1:
        return list
    pivot=list[0] # 기준점
    tail=list[1:] # 기준점을 제외한 나머지부분
    left_side=[x for x in tail if x<= pivot] # 기준점보다 작은 값들
    right_side=[x for x in tail if x> pivot] # 기준점보다 큰 값들
    
    return quickSort(left_side)+[pivot]+quickSort(right_side)

print(quickSort([4, 3, 2, 5, 1]))

시간복잡도는 O(N*longN)이다. (최악의 경우 O(N^2))

---

삽입정렬(Insert Sort)

이해하기

 삽입정렬은 key로 설정한 값보다 크면 오른쪽으로 한칸씩 옮겨 key를 적당한 위치에 삽입하여(Insert) 정렬하는 방법이다. key보다 작을 경우는 왼쪽에 남겨둔다.

4

3(Key)

2

5

1

 위와 같은 수열이 있다고 하면 먼저 3을 키로 정한다. 그리고 앞에 있는 4와 비교한다. 4보다 3이 작으므로 4를 뒤로 한 칸 당기고 원래 4의 자리에 3을 넣는다.

3

4

2(Key)

5

1

  그 다음 키는 2이고, 앞에 있는 4와 비교했을 때 4보다 작으므로 4를 2의 자리에 넣어주고, 2은 그대로 넣는 것이 아니라 그 앞의 3과 비교를 해준다. 2가 3보다 작으므로 2의 위치는 제일 앞이 되고, 3은 뒤로 또 한 자리 밀린다.

2

3

4

5(Key)

1

 그 다음키는 5이다. 5를 앞자리의 4와 비교해서 4보다 크므로 그대로 둔다.

2

3

4

5

1(Key)

 마지막으로 키인 1을 5와 비교하면 5보다 1이 작으므로 5는 뒤로 한 자리 밀리고, 1과 4를 비교하게 된다. 1이 4보다 작으므로 4는 또 한 자리 뒤로 밀리고, 그 다음 3와 1을 비교한다. 3보다 1이 작으므로 3이 한 자리 뒤로 밀리고, 마지막으로 2와 비교해서 1이 작으므로 1은 제일 앞으로 가게 된다.

1

2

3

4

5

코드로 나타내기

 이해하기를 토대로 삽입정렬의 포인트를 정리해보면 아래와 같다.

1. 인덱스 1번자리의 숫자를 key로 정하고 앞수들과 비교하며 앞으로 당겨온다.

def InsertSort(numList):
    for i in range(1, len(numList)): # key의 경우의 수는 제일 앞에 있는 수를 뺀 나머지 수들. 제일 앞에 있는 수는 두번째 수를 key로 할 때 위치가 정해진다.
        key=numList[i] # key값을 설정하고,
        j=i-1 # j는 key값 앞에 있는 수의 index이다. numList[j]가 key값 앞에 있는 수.
        while j>=0 and key<numList[j]: # key값이 앞에 있는 수보다 작다면,
            numList[j+1]=numList[j] # key값 앞에 있는 수를 뒤로 한 칸 밀고,(=key값의 자리로 밀고)
            j-=1 # key 앞의 수가 하나가 아니라 여러 개일 수 있으므로, key 앞의 수들을 다 가져다가 비교한다.
        numList[j+1]=key # key값이 앞에 있는 수보다 크다면, 그 수의 다음 자리에 key를 넣어준다.
    return numList

시간복잡도는 O(N^2)이다.

---

병합정렬(Merge Sort)

이해하기

 요소를 쪼개고, 합치는(Merge) 과정에서 정렬을 시키는 방법이다.

4

3

2

5

1

 위와 같은 수열이 있을 때를 생각해보자. 우선 수열을 반으로 쪼갠다.

4

3

2

5

1

 그리고 빨간색 숫자들과 파란색 숫자들을 각각 또 반으로 나눈다.

 먼저 빨간색 숫자들을 나눠 보자.

4

3

 나눈 결과 왼쪽과 오른쪽은 각각 하나의 숫자가 되고 4와 3을 비교하여 정렬하게 된다.

 그렇게 되면 아까 처음에 나눴던 왼쪽부분과 오른쪽부분은 아래와 같아진다.

3

4

2

5

1

 이제는 오른쪽 부분을 계속 쪼갠다.

2

5

1

5

1

 5와 1을 비교하면 1이 더 작으므로 둘의 자리가  바뀐다. 이제 쪼개기가 끝났으므로 쪼갠 수열들을 하나 하나 합쳐간다.

2

1

5

 이제 2와 정렬된 오른쪽 1과 5를 비교하여 2의 위치를 찾는다. 정렬한 결과는 아래와 같다.

1

2

5

 이제 오른쪽은 정렬이 끝났으므로 결과는 아래와 같다.

3

4

1

2

5

 이제부터는 왼쪽부분의 수들을 하나씩 꺼내어 오른쪽부분의 수들과 비교한다. 제일 처음엔 왼쪽부분과 오른쪽부분의 제일 앞에 있는 수 3과 1을 비교한다. 1이 3보다 작기 때문에 결과배열의 제일 앞에 1이 들어간다. 그리고 3과 2를 비교해서 2가 더 작으므로 2는 결과배열의 1의 옆자리에 들어간다. 그리고 마지막으로 3과 5를 비교해서 3이 더 작으므로 세번째 자리에는 3이 들어가게 된다. 현재까지의 결과배열은 아래와 같다.

1

2

3

 이제 남아있는 4와 정렬되지 않은 5를 비교한다. 4가 더 작으므로 4를 앞에 넣어주고 그 다음 5를 넣어준다. 그럼 정렬이 완료된다.

1

2

3

4

5

코드로 나타내기

 이해하기를 토대로 병합정렬의 포인트를 정리해보면 아래와 같다.

1. 배열을 왼쪽 오른쪽으로 나누는 쪼개기를 배열의 숫자가 1개가 될 때까지 계속 반복한다.

2. 쪼갠 배열부터 숫자를 비교해가며 정렬시킨다.

3. 처음 나눴던 큰 두 배열로 돌아오면 왼쪽에 있는 수를 하나 꺼내어 오른쪽에 있는 수들과 비교하며 작은 수들을 꺼낸다.

(+) 쪼개어 정렬시킨다는 점에서 퀵 정렬과 같지만 퀵 정렬은 pivot을 기준으로 작은 값과 큰 값의 배열로 쪼갠다.

반면 병합정렬은 기준점이 없이 그냥 두 배열로 쪼갠다.

def mergeSort(numList):
    if len(numList)>1: # 리스트의 길이가 1이 될 때까지 리스트를 쪼갠다.
        middle=len(numList)//2
        left=numList[:middle]
        right=numList[middle:]

        mergeSort(left) # 재귀함수. 위에서 만든 left를 계속 쪼갠다.
        mergeSort(right) # 재귀함수. 위에서 만든 right를 계속 쪼갠다.

        i = j = k= 0

        while i<len(left) and j<len(right): # left와 right가 아직 있을 때
            if left[i]<right[j]: # 왼쪽리스트의 값이 더 작다면
                numList[k]=left[i] # 리스트의 값을 왼쪽리스트의 값으로 바꿔준다.
                i+=1 # 그리고 왼쪽리스트의 빠진 값 다음값과 비교해야하므로 +1을 해준다.
            else: # 오른쪽리스트의값이 더 작다면
                numList[k]=right[j] # 리스트의 값을 오른쪽리스트의 값으로 바꿔준다.
                j+=1 # 그리고 오른쪽리스트의 빠진 값 다음값과 비교해야하므로 +1을 해준다.
            k+=1 # 이미 왼쪽리스트의 값으로든 오른쪽리스트의 값으로든 리스트의 값이 바뀌었으므로 리스트의 다음칸으로 간다.

        while i<len(left): # 왼쪽에 아직 정렬되지 않은 값이 남아있다면
            numList[k]=left[i] # 합쳐진 리스트에 그 값을 넣는다.
            i+=1
            k+=1

        while j<len(right): # 오른쪽에 아직 정렬되지 않은 값이 남아있다면
            numList[k]=right[j] # 합쳐진 리스트에 그 값을 넣는다.
            j+=1
            k+=1

        return numList

 쪼개는 과정에서 log n의 시간복잡도, 합치는 과정에서 n의 시간복잡도, 결국 nlog n의 시간복잡도가 된다.

 

---

계수정렬(Counting Sort)

이해하기

 계수정렬은 여러 개의 칸을 만들어 각 칸마다 그 칸 인덱스의 숫자가 수열에 몇 번 등장했는지 세서 정렬시키는 방법이다.

4

2

2

10

7

 위와 같은 수열이 있다고 하면 수열 중 가장 큰 숫자는 10이므로 총 11개의 칸을 만든다. 인덱스는 0부터 시작이므로 편의상 1칸을 더 만들어준다. 그리고 수열을 돌며 각 숫자가 등장하는 횟수를 각 칸에 넣어준다. 처음 4가 등장했으므로 아래와 같다.

0	1	2	3	4	5	6	7	8	9	10
				1

그리고 다음 숫자들도 순서대로 해주면 결과는 아래와 같다.

0	1	2	3	4	5	6	7	8	9	10
		2		1			1			1

 이제 이 배열을 앞에서부터 봐가면서 개수에 맞춰 인덱스를 꺼내면 정렬이 끝난다.

2

2

4

7

10

코드로 나타내기

 이해하기를 바탕으로 계수정렬의 포인트를 정렬하면 아래와 같다.

1. 수열에서 제일 큰 숫자+1만큼의 배열 공간을 만들어준다.

2. 수열 앞에서부터 그 숫자가 등장하는 횟수를 배열 공간에 넣어준다.(인덱스가 그 숫자가 된다.)

3. 수열을 다 돌아 공간을 채웠으면 그 배열을 앞에서부터 보면서 숫자를 개수만큼 꺼내서 정렬시킨다.

def countingSort(list):
    result=[]
    cnt=[0]*(max(list)+1)

    for i in range(len(list)):
        cnt[list[i]]+=1

    for i in range(len(cnt)):
        for j in range(cnt[i]):
            result.append(i)

    return result

 시간복잡도는 O(N+K)이다. (K는 정렬할 수들 중 가장 큰 값을 의미한다.)