[파이썬 자료구조 6단원] - 정렬 알고리즘

정렬이란?

키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업

 

오름차순 : 작은 데이터를 앞쪽에 늘어놓는 작업

내림차순 : 큰 데이터를 앞쪽에 늘어놓는 작업

 

 

버블정렬

버블정렬이란 이웃한 두 원소의 대소 관계를 비교하여 필요에따라 교환을 반복하는 알고리즘으로 단순 교환정렬이라고도 한다.(안정적이다.)

 

패스(pass) : 원소의 비교, 교환하는 과정을 의미한다.

셰이커정령(양방향버블정령)

 

 

 

단순 선택 정렬

단순선택정렬 과정

1. 아직 정렬하지 않는 부분에서 값이 가장 작은 원소 a[min]을 선택한다.

2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.

(안정적이지 않다.)

 

 

 

단순 삽입 정렬

단순 삽입 정렬이란 주목한 원소(두번째 원소부터 주목한다)보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 방법이다.

(아직 정렬되지 않은 부분의 맨 앞의 원소를 정렬된 부분의 알맞은 위치에 삽입한다.)

 

 

 

셸 정렬

셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행하는 방법이다.

(안정적이지 않다.)

 

4-정렬(서로 4칸 떨어진 원소를 정렬하는 방법) 시행 후

2-정렬(서로 2칸 떨어진 원소를 정렬하는 방법) 시행 그리고

1-정렬(서로 1칸 떨어진 원소를 정렬하는 방법) 시행 

마지막으로 단순 삽입 정렬을 한 번 수행하여 정렬을 완료함.

(여기서 h = 4,2,1)

 

셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해 사용한다.

(h는 서로 배수가 되지 않게 하는게 좋다.)

 

 

 

퀵 정렬

퀵 정렬은 가장 빠른 정렬 알고리즘으로 많이 사용된다.(안정적이지 않다.)

그룹을 나누는 피벗(기준)을 선택하고 각 그룹에서 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료되는 것이다.

피벗은 어떤 값으로 선택하느냐에 따라 배열을 나누는것과 정렬하는 성능에 영향을 미친다.

 

 

 

sorted( ) 함수로 정렬하기

파이썬에서는 정렬을 수행하는 sorted( )함수를 내장 함수로 제공한다.

이 함수는 전달받은 함수를 list형으로 반환한다.

 

x = sorted(x) -----------오름차순

 

x = sorted(x, reversed = True) ------------내림차순

 

 

 

병합 정렬

병합정렬은 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합화하는 작업을 반복하는 알고리즘이다.

(안정적이다.)

 

 

 

힙 정렬

힙 정렬은 힙의 특성을 이용하여 정렬하는 알고리즘이다. '힙에서 최대값은 루트에 위치한다'는 특징을 이용하여 정렬하는 방식이다.

 

heapq 모듈을 사용하여 힙 정렬을 구현할 수 있다.

파이썬의 heapq 모듈은 힙에 원소를 추가하는 heappush( )함수와 힙에서 원소를 제거하는 heappop( ) 함수를 제공한다.

 

 

 

도수 정렬

도수 정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘이다.(안정적이다.)

 

 

 

두 배열을 병합하기

빠르게 병합하기 위해서 heapq 모듈의 merge( ) 함수를 사용하면 된다.

 

import heapq

 

a = [2,,4,6,8,11,13]

b = [1,2,3,4,9,16,21]

 

c = list(heapq.merge(a,b))