[ 자료구조 ] 정렬 알고리즘 (Sorting Algorithms)

1. 선택 정렬(앞부터 i, i+1 비교) O(n^2)

def selectionSort(array):

    n = len(array)
    for i in range(n-1):
        minIdx = i
        for k in range(i + 1, n):
            if (array[minIdx] > array[k]):
                minIdx = k
        array[i], array[minIdx] = array[minIdx], array[i]

    return array

i(0, n-1): min값에 i를 저장, 한 사이클 끝나면 min과 i의 값을 스왑

k(i+1, n): k값과 min값을 비교하면서 min값보다 k값이 작으면 min에 k값 대입

= i와 i+1값을 비교해 값을 바꿔주는 정렬

---

2. 삽입 정렬(앞부터 범위, 뒤부터 비교) O(n^2)

• [x] 코드 암기

def insertionSort(array):
   
    n = len(array)
    for end in range(n):
        for cur in range(end, 0, -1):
            if(array[cur - 1] > array[cur]):
                array[cur - 1], array[cur] = array[cur], array[cur - 1]
    return array

end(1, n): cur이 비교할 범위를 정해준다. 처음 1 → 늘려가며 비교

cur(end, 0, -1): end부터 0까지 -1하면서 내려오고 만약 cur-1값이 cur값보다 크면 cur-1과 cur을 스왑

= cur이 한번 움직일 때 마다 비교하고 cur-1값이 cur보다 크면 스왑

3. 버블 정렬 (가장 큰 값 뒤에 놓고 순회) O(n^2)

• [x] 코드 암기

def bubble_sort(array):
   
    n = len(array)
    for i, end in enumerate(range(n - 1, 0, -1)):
        is_change = False
        for curr in range(0, end):
            if array[curr] > array[curr + 1]:
                array[curr], array[curr + 1] = array[curr + 1], array[curr]
                is_change = True 
        print(i + 1, "번째 사이클: ", array)
        if not is_change:
            break
    return array

end(n-1, 0, -1): curr이 비교할 범위를 정해준다. 처음 n-1 → 줄여가며 비교

curr(0, end): 0부터 end까지 비교하면서 올라가고 만약 curr값이 curr-1값보다 크면 curr-1과 curr값을 스왑

= 스왑 할 시 플래그 값을 변경시켜 스왑했다고 알림, end사이클 1번 반복 할 동안 한번도 스왑이 일어나지 않았다면 정렬된 리스트이기 때문에 반복문 탈출

= cur 한 사이클을 돌면 제일 큰 값이 맨 뒤에 놓인다. 계속 반복시 완전히 정렬

4. 퀵 정렬 (재귀 함수를 이용) O(nlogn) ~ O(n^2)

def q_sort(array, start, end):
  
    if end == start:
        return

    low = start
    high = end

    pivot = array[(low + high) // 2]
    while low <= high:
        while array[low] < pivot:
            low += 1
        while array[high] > pivot:
            high -= 1
        if low <= high:
            array[low], array[high] = array[high], array[low]
            low, high = low + 1, high - 1 

    mid = low
    q_sort(array, start, mid - 1)
    q_sort(array, mid, end)

def quick_sort(array):
    q_sort(array, 0, len(array)-1)

재귀 함수를 사용해서 pivot값을 중심으로 반 씩 나눠 정렬하는 방식이다.

만약 정렬할 배열의 길이가 1이하인 경우 return해야한다. → 정렬할 요소가 없음.

정렬은 low≤high일 경우 계속된다.

pivot값보다 low값이 작은 경우 low+=1, high값이 큰 경우 high-=1

low, high 비교를 끝내고 low≤high일 경우 low, high 스왑 후 low, high값 증감

5. 실습 - 리스트 앞, 뒤 값 묶어서 리스트 반환 함수

def generate_group(array):
    all = []

    while len(array) != 0:
        all.append([array[-1][0], array[0][0]])
        array = array[1:-1]
    return all

6. 중간값 기준으로 binary 이미지 생성하는 함수

h, w = array.shape  
    for i in range(h):
        for j in range(w):
            if array[i][j] <= mid_value:
                array[i][j] = 0
            else:
                array[i][j] = 255

7. 배열에서 중복이 제거된 배열 반환 함수

def remove_duplicate(array):

    new_array = []
    for i in array:
        if i not in new_array:
            new_array.append(i)
        
    return new_array

8. 선택 정렬의 개념

여러 데이터 중에서 가장 작은 값을 뽑는 작동을 반복하여 값을 정렬하는 방식이다.

9. 삽입 정렬의 개념

기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하는 정렬 방법을 사용한다.

10. 정렬된 배열에서 중앙값을 찾는 방법

pivot = array[len(array) // 2]

11. 버블 정렬의 개념

첫 번째 값부터 시작해서 바로 앞뒤 데이터를 비교하여 큰 것은 뒤로 보내는 방법을 사용한다.

각 사이클이 끝날 때마다 마지막 위치에 가장 큰 데이터가 자리잡는다.

데이터 1개를 제외하고 대부분 정렬되어 있는 배열일 경우 연산 수가 급격히 줄어든다.

12. 퀵 정렬의 개념

**기준(pivot)**을 하나 뽑은 후 기준보다 작은 그룹과 큰 그룹을 나누어 다시 각 그룹을 정렬하는 방법이다.

나눈 그룹을 다시 정렬하고자 재귀 호출을 하고, 각 그룹의 정렬이 완료되면 합치는 방식을 사용한다.