삽입 정렬

• 막대기를 기준으로 왼쪽의 데이터는 이미 정렬되어있다고 가정
• 막대기를 기준으로 오른쪽의 제일 처음 데이터가 추가되었을때 왼쪽의 데이터들중 어디에 삽입되는 것이 가장 적당한 것인지를 비교
• 추가된 데이터는 막대기를 기준으로 왼쪽의 데이터들 중 가장 오른쪽 부터 비교해가면서 필요시 SWAP하면서 적당한 삽입 위치를 선정

• A[0]는 dummy값으로 '-무한대'라고 가정하고, A[1]부터 원래 배열이 시작된다.
• 맨앞이 '-무한대'라고 가정함에 따라 배열의 첫번째 원소는 반드시 정렬되어 있음을 보장한다.

• 제자리성
  • 제자리 정렬
  • i, j, Value등 상수 크기 메모리
• 안정성
  • 안정된 정렬
  • 인접한 레코드끼리만 자리바꿈
• 시간복잡도
  • 최악시간복잡도 = O(n2)
  • ex) 역순으로 이미 정렬된 레코드 = 2+3+…+n = n(n+1)/2-1
  • 최선시간복잡도 = O(n)
  • ex) 이미 정렬된 레코드 = n-1번 비교
    -> 만약 대부분의 데이터가 이미 정렬이 되어있다면 삽입정렬은 매우 효과정인 정렬방법이다.
  • 평균시간 복잡도 = O(n2)

쉘 정렬

• 삽입정렬은 비교를 통해 최대 한칸만 이동할 수 있다는 한계가 있다.
• 쉘 정렬은 h값에 따라 그룹으로 나누어 각 그룹의 같은 순서끼리 비교해 삽입정렬과 마찬가지로 정렬한다.
  -> 따라서 삽입정렬과 다르게 한칸이 아닌 여러칸을 움직일 수도 있다.
  -> 이후 쉘의 크기를 1로 바꾸어서 이때부터는 삽입정렬과 마찬가지로 수행을 하여 정렬하게 된다.
• 만약 거의 정렬된 배열이 있을 때, SWAP이 필요한 두 원소가 매우 멀리 떨어져있다면 이 두 원소만을 SWAP하기 위해 한칸씩 이동해야 하는 삽입정렬은 매우 비효율적이다. 따라서 쉘정렬을 통해서 여러칸을 움직인다음에 그래도 남아있는 정렬되지 않은 원소들만 삽입정렬을 통해 정렬한다.

• 적절한 h값을 선택하는 알고리즘이 포함된다

• 제자리성
  • 제자리 정렬
  • i, j, Value 등 상수 크기 메모리
• 안정성 : 불안정
• 최악시간복잡도
  • n3/2 when h=1,4,13,40,…
    

퀵 정렬

• 퀵 정렬은 분할 함수에 의해 작동한다
• 분할 함수란 배열의 맨 처음 원소를 분할 원소라고 지정하고, 분할 원소를 적당한 위치에 위치시켜서 분할원소를 기준으로 왼쪽에는 분할원소보다 작은값, 오른쪽에는 분할원소보다 큰 값이 오게 한다.

분할함수 설계

• 배열의 첫번째 원소를 분할원소로 지정하고, 분할원소의 다음 원소부터 분할원소보다 크거나 같은 원소가 제일처음나온 값을 Left Pointer로 지정. 마찬가지로 분할원소를 기준으로 오른쪽부터 분할원소보다 같거나 작은 원소가 제일 처음나온 값을 Right Pointer라고 지정.
• Right가 Left보다 오른쪽에 위치한다면 순서가 역전된것이므로 두 값을 SWAP한다.
• 이러한 과정을 반복하는중에 Right가 Left보다 왼쪽에 있다면 분할원소를 Right와 SWAP후 분할함수는 종료된다.
• 1 2 3 4 5 OR 5 4 3 2 1 과 같이 특수한 배열같은 경우는 Right와 Left값을 따로 지정해줘야 한다.

• 맨 오른쪽에 더미값을 '무한대'로 지정함에 따라 5 4 3 2 1과 같은 배열에서 위치확인을 통해 Left값을 지정해줘야 하는 비효율성을 해결할 수 있다.

퀵 정렬 설계

• 위에서 설계한 분할함수를 이용해서 퀵 정렬을 설계한다.
• 분할함수에 의해서 분할원소가 적절한 위치에 위치되어있다면, 분할원소의 왼쪽에 배열들에 분할함수를 다시 반복한다. 마찬가지로 분할원소의 오른쪽 배열에도 수행한다. 이러한 과정을 반복한다.

• 재귀함수를 통해 왼쪽 그룹과 오른쪽 그룹에 대해 분할함수를 반복한다.

• 제자리성
  • 제자리 정렬 (단, 순환함수의 임시변수 및 복귀 주소 저장용 메모리가 추가 사용됨)
• 안정성
  • 불안정
• 시간복잡도
  • 평균시간복잡도 = O(nlogn)
  • 최악시간복잡도 = O(n2)
  • Ex) 분할원소가 항상 가장 큰 key이거나 가장 작은 key인 경우