정렬

정렬이란?

 

섞여 있는 데이터를 순서대로 나열하는 것

 

대표적인 정렬의 종류

O(n²)의 시간 복잡도

- 버블 정렬(Bubble Sort)

- 선택 정렬(Selection Sort)

- 삽입 정렬(Insertion Sort)

 

O(n log n)의 시간 복잡도

- 병합 정렬(Merge Sort)

- 퀵 정렬(Quick Sort)

 

※ 시간 복잡도

 

위로 갈수록 간단하고, 아래로 갈수록 복잡해진다.

 

- O(1)과 같은 상수(constant) 형태

- O(log n)과 같은 로그(logarithmic) 형태

- O(n)과 같은 선형

- O(n log n) 과 같은 선형로그 형태

- O(n^c), O(n³)과 같은 다차(polynomial) 형태

- O(c^n), O(3^n)과 같은 지수(exponential) 형태

- O(n!)과 같은 팩토리얼(factorial) 형태

 

 

버블 정렬

- 인접한 두 수를 비교하며 정렬해나가는 방법 O(n²)의 느린 성능

- 구현 방법은 가장 단순하나 최대 시간 복잡도를 가짐

 

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
for i in range(1, len(a)): # 리스트의 크기만큼 반복
    for j in range(0, len(a)-1): # 각 회전당 정렬이 끝나지 않은 친구들을 위해 반복
        if a[j] > a[j+1]: # 현재 인덱스의 값이 다음 인덱스의 값보다 크면 실행
           a[j+1], a[j] = a[j], a[j+1] # swap해서 위치 바꾸기
print(a) # 정렬 후 리스트

#출력
#정렬 전
[4, 9, 2, 5, 7]
#정렬 후
[2, 4, 5, 7, 9]

 

선택 정렬

- 한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬

- 불안정 정렬이며 최대 시간복잡도(O(n²))를 가짐

-가장 원시적인 방법으로 '매번 가장 작은 것을 선택한다'는 의미에서 선택정렬 알고리즘

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a)# 정렬 전 리스트
for i in range(len(a)-1): # 리스트의 크기-1만큼 반복
    for j in range(i+1, len(a)): # 해당 인덱스+1부터, 리스트 크기만큼 반복
        if a[i] > a[j]: # 인덱스의 값이 비교 인덱스보다 더 크다면
            a[i] , a[j]  = a[j], a[i] # swap 해주기
print(a) # 정렬 후 리스트

#출력
#정렬 전
[8, 4, 7, 2, 3]
#정렬 후
[2, 3, 4, 7, 8]

 

삽입 정렬

- 정렬된 데이터 그룹을 늘려가며 추가되는 데이터는 알맞은 자리에 삽입

- 특정한 데이터를 적절한 위치에 '삽입'한다는 의미에서 삽입 정렬

- 안정 정렬

- 길어질수록 효율 극악, 하지만 필요한 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 효율적

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 11의 난수 5개 리스트로 생성
print(a)# 정렬 전 리스트
for i in range(1, len(a)): # 리스트의 크기만큼 반복
    for j in range(i, 0, -1): # j 인덱스의 값이 줄어드면서 삽입할 위치를 찾을 때까지 반복
        if a[j] < a[j-1]: # 현재 인덱스가 앞의 원소보다 작다면
            a[j], a[j-1] = a[j-1], a[j] # swap해서 값 뒤로 밀어내기
        else : break # 불필요한 반복을 피하기 위해 break
print(a)# 정렬 후 리스트 출력

#출력
#정렬 전
[8, 9, 3, 1, 6]
#정렬 후
[1, 3, 6, 8, 9]

 

병합 정렬

- 분할 정복과 재귀를 이용한 알고리즘으로 O(n log n)의 시간 복잡도를 가지고 있어 좋은 성능을 보임

- 반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되며 이 과정에서 2n 개의 공간이 필요

- 대부분의 경우 퀵 정렬보다는 느리지만 일정한 실행 속도뿐만 아니라 무엇보다도 안정 정렬이라는 점에서 상용 라이브러리에 많이 쓰임

 

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
def mergeSort(a):
    if len(a) > 1: # 배열의 길이가 1보다 클 경우 재귀함수 호출 반복
        mid = len(a)//2 # 2로 나눈 몫 (중간 값) 취함
        la, ra = a[:mid], a[mid:] # la 중간 값을 기준으로 왼쪽, ra 중간 값을 기준으로 오른쪽
        mergeSort(la) # 왼쪽 서브 리스트의 값을 기준으로 병합정렬 재귀 호출
        mergeSort(ra) # 오른쪽 서브 리스트의 값을 기준으로 병합정렬 재귀 호출
        li, ri, i = 0, 0, 0 # 정렬을 위한 변수 선언 (왼쪽, 오른쪽, 기준)
        while li < len(la) and ri < len(ra): # 서브 리스트의 정렬이 끝날 때까지 반복
            if la[li] < ra[ri]: # 오른쪽 리스트의 값이 클 경우라면
                a[i] = la[li] # 왼쪽 리스트의 해당 인덱스의 값을 할당
                li += 1 # 왼쪽 리스트의 인덱스 하나 증가
            else: # 왼쪽 리스트의 값이 클 경우라면
                a[i] = ra[ri] # 오른쪽 리스트의 해당 인덱스의 값을 할당
                ri += 1 # 오른쪽 리스트의 인덱스 하나 증가
            i += 1 # 기준 인덱스 증가
        a[i:] = la[li:] if li != len(la) else ra[ri:]
      # 왼쪽 리스트의 인덱스의 값이 서브 리스트의 값과 같지 않을 경우라면(정렬 끝),
      # 왼쪽 서브 리스트의 값을 리스트에 덮어쓰기, 그렇지 않은 경우라면 오른쪽 서브 리스트의 값 할당                                   
mergeSort(a)
print(a) # 정렬 후 리스트

#출력
#정렬 전
[3, 2, 5, 9, 6]
#정렬 후
[2, 3, 5, 6, 9]

 

퀵 정렬

- 가장 많이 사용되는 정렬 알고리즘 중 하나

- 분할 정복 알고리즘으로 평균적으로 빠른 속도 수행

- 추가적인 메모리가 공간이 필요 없다는 장점을 가짐

-다른 정렬 알고리즘보다 빠르며 많은 언어의 정렬 내장 함수로 퀵 정렬을 수행

- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작

 

import random # random 메소드 사용을 위해 import

a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트
def quickSort(a, start, end):# 재귀함수용 함수 선언(리스트, 시작인덱스, 종료인덱스)
    # print(a)
    if start < end: # 시작 인덱스 보다 끝 인덱스가 클 경우
        left = start # left 변수에 시작 인덱스 할당
        pivot = a[end] #  //pivot 값은 a리스트에 마지막 원소 값
        for i in range(start, end): # 시작인덱스부터 끝 원소까지 반복
            if a[i] < pivot: # 리스트 인덱스 값이 pivot 값보다 작을 경우라면
                a[i], a[left] = a[left], a[i] #  해당 인덱스와 left인덱스  swap
                left += 1 # 인덱스 하나 증가 시켜주기(자리를 옮겨가며 비교해야 하기 때문에)
        a[left] , a[end] = a[end], a[left] # left인덱스와 끝 인덱스 swap
        print(left)
        quickSort(a, start, left-1) # 재귀 호출 (리스트, 시작 인덱스, left-1)
        quickSort(a, left+1, end) # 재귀 호출 (리스트, left+1, 종료인덱스)
quickSort(a, 0, len(a)-1)
print(a) # 정렬 후 리스트

#출력
#정렬 전
[8, 1, 7, 2, 5]
#정렬 후
[1, 2, 5, 7, 8]

 

파이썬 내장 정렬 메소드

- 특별한 경우가 아니면 파이썬에서 제공하는 내장 메소드를 통해 편리하게 정렬을 진행할 수 있음

import random # random 메소드 사용을 위해 import
a = random.sample(range(1, 10), 5) # 1<= x < 10의 난수 5개 리스트로 생성
print(a) # 정렬 전 리스트 출력
a.sort() # 오름차순 정렬
print(a) # 정렬 후 리스트 출력
a.sort(reverse=True) # 내림차순 정렬
print(a) # 정렬 후 출력
print(sorted(a)) # sorted 함수 사용 정렬
print(sorted("This is a Moon's world".split(), key=str.lower)) # sorted 함수를 이용한 키 값 기준 정렬
b= [('abc','A',3), ('bcd','B',1), ('cde','C',15)] # 불특정 tuple을 갖는 리스트 생성
print(sorted(b, key=lambda b: b[2])) # tuple의 2번 째 요소를 가지고 정렬

# 출력
[4, 5, 8, 2, 6]
[2, 4, 5, 6, 8]
[8, 6, 5, 4, 2]
[2, 4, 5, 6, 8]
['a', 'is', "Moon's", 'This', 'world']
[('bcd', 'B', 1), ('abc', 'A', 3), ('cde', 'C', 15)]

 

안정 정렬 vs 불안정 정렬

- 안정 정렬 : 병합 정렬, 버블 정렬, 삽입 정렬

- 불안정 정렬 : 퀵 정렬, 선택 정렬

 

안정 정렬 : 기존 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이루어짐

불안정 정렬 : 시간 순으로 정렬한 값을 지역명으로 재정렬하면 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞임