Sorting 알고리즘 기초개념 및 구현실습

2019-04-21

.

그림, 실습코드 등 학습자료 출처 : https://github.com/ythwork

1) 참고사이트 : https://github.com/ythwork

2) 참고서적 : Hello Coding 그림으로 개념을 이해하는 알고리즘 (아디트야 바르가바 지음, 김도형 옮김 / 한빛미디어)

1. Quick Sort (퀵정렬)

  • 현업에서 많이 사용되는 빠른 정렬 기법

1) 분할정복기법 (Divide and conquer)을 활용한다.

(문제를 분할하여 해결, 재귀 함수를 이용)

기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측에, 기준값보다 큰 데이터는 우측으로 분할하고 다시 퀵 정렬을 적용한다.

2) 통상 \(\ O(nlogn)\)이고, 이미 정렬 된 데이터의 경우(최악의 경우) \(\ O(n^2)\) 를 보이기도 한다.

퀵소트의 경우 이미 정렬 된 데이터에 대해서 최악의 효율을 보입니다. 피벗이 한쪽 끝으로 오게 되어서 파티션을 나눌 때 균형이 완전히 무너지고 한 번 정렬에 데이터가 하나씩 떨어져 나가게 됩니다. 따라서 데이터가 n개라면 n과 거의 동일한 수의 단계를 거쳐야 합니다. 그래서 결과적으로 이미 정렬 된 데이터에 대해 효율은 \(\ O(n^2)\)이 됩니다.

3) 작동원리

입력 : [7,5,3,5,4,2,8]

출력 : [2,3,4,5,5,7,8]

1

4) 파이썬 코드구현

import random

def get_pivot_index(li, start, mid, end):
    idx_li=[start, mid, end]
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1]=idx_li[1], idx_li[0]
    if li[idx_li[1]] > li[idx_li[2]]:
        idx_li[1], idx_li[2]=idx_li[2], idx_li[1]
    if li[idx_li[0]] > li[idx_li[1]]:
        idx_li[0], idx_li[1]=idx_li[1], idx_li[0]
    
    return idx_li[1]

def quick_sort(li, start, end):
    if start >= end:
        return
    
    left=start
    right=end
    
    mid=(start+end)//2
    pivot_idx=get_pivot_index(li, start, mid, end)
    li[mid], li[pivot_idx]=li[pivot_idx], li[mid]

    pivot=li[mid]
    while left <= right:
        while li[left] < pivot:
            left+=1
        while li[right] > pivot:
            right-=1
        
        if left <= right:
            li[left], li[right]=li[right], li[left]
            left+=1
            right-=1

    quick_sort(li, start, right)
    quick_sort(li, left, end)

if __name__=="__main__":
    data=[7,5,3,5,4,2,8]
    print("input : ", data)
    quick_sort(data, 0, len(data)-1)
    print("output : ", data)

input :  [7, 5, 3, 5, 4, 2, 8]
output :  [2, 3, 4, 5, 5, 7, 8]
  • 빅오계산

2

2. Bubble Sort (거품정렬)

  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

  • 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.

  • 구현하기 쉬운 것이 특징이다.

  • 작동원리

입력 : [7,2,4,9]

출력 : [2,4,7,9]

3

  • 파이썬 코드 구현
import random

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

if __name__=="__main__":
    data=[7,2,4,9]
    print("input : ",data)
    bubble_sort(data)
    print("output : ", data)

input :  [7, 2, 4, 9]
output :  [2, 4, 7, 9]
  • 빅오계산

데이터 개수가 4개일때

7 9 비교 ,2 9 비교, 4 9비교 3번

7 2 비교, 7 4 비교 2번

2 4 비교 1번

총 6번 비교

등차수열로 늘어나게 되므로 빅오는 O(n제곱) 이다.

다시말해 데이터가 많아질수록 엄청나게 늘어나게 된다.

3. Selection Sort (선택정렬)

  • 빅오 : \(\ O(n^2)\)

  • 최소값을 선택하는 과정을 반복해서 선택 정렬이라 부른다고 한다.

step1) 주어진 리스트 중에 최솟값을 찾는다.

step2) 그 값을 맨 앞에 위치한 값과 교체한다.

step3) 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

  • 파이썬 코드구현
import random

def findSmallest(li):
    smallest = li[0]
    smallest_index = 0

    for idx in range(1,len(li)):
        if li[idx] < smallest:
            smallest = li[idx]
            smallest_index = idx
    
    return smallest_index

def selectionSort(li):
    
    result = []
    
    for count in range(len(li)):
        smallest = findSmallest(li)
        result.append(li.pop(smallest))
        
    return print("정렬 후 리스트 :", result)


li = [random.randint(1,10000) for data in range(10)]
print("정렬 전 최초 리스트 :", li )

selectionSort(li)

정렬 전 최초 리스트 : [9382, 1201, 6871, 7670, 2424, 2215, 11, 157, 4188, 9456]
정렬 후 리스트 : [11, 157, 1201, 2215, 2424, 4188, 6871, 7670, 9382, 9456]