정렬(1)

정렬(sort)이란 2개 이상의 배열을 특정기준에 의해 재배열 하는 것을 의미한다.

아래에 제시한 정렬방법은 모두 오름차순이다. ex) 2 3 5 6 7 9 ...

 

---

1. 버블 정렬 (bubble sort)

 

이중 반복물을 이용해서 인접한 두 개의 원소를 반복비교해 자리를 교환하는 방식을 이용한다. 자료가 n개면 n-1번 비교를 n번 반복해야 하기 때문에 시간복잡도는 O(n^2)이다.

 

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

*** 함수이름에는 식별자로 스네이크 케이스를 이용하였다.

---

2. 선택 정렬 (selection sort)

 

     1) 주어진 배열에서 최솟값을 찾는다.

     2) 그 최솟값을 맨 앞에 위치한 것과 바꾼다.

     3) 맨 앞의 것을 제외하고, 나머지 것들을 대상으로 다시 위 (1)~(2) 과정을 반복한다.

 

바꾸는 행위(swap)는 버블 정렬보다 적을 수 있지만, 이중 반복문이기 때문에 시간복잡도는 마찬가지로 O(n^2)

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

---

3. 삽입 정렬 (insertion sort)

선택한 요소의 앞부분을 보면서 들어갈 자리를 찾아가는 정렬방법이다.

 

2번째 인덱스부터 시작해서 그 앞과 자신을 비교하고, 내가 더 크면 더 이상 비교하지 않고 다음 인덱스로 넘어간다.

만약 내가 더 작았다면 그 앞에 있던 원소를 한 칸 뒤로 밀고, 자신은 그보다 한칸 더 앞에 있던 원소와 비교를 진행한다.

앞보다 내가 더 커서 더 이상 비교를 진행하지 않아도 되면, 비어 있는 칸에 자신을 위치시킨다.

 

기본적으로는 시간 복잡도가 O(n^2)이지만 어느 정도 정렬이 된 배열이였다면 효율이 높아지게 된다.

 

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]

 

 

다음 포스트부터는 알고리즘은 복잡하지만 시간복잡도를 줄일 수 있는 정렬 방법들을 알아보도록 하자.