HW14

아래 배열을 이용해 다음 6가지 정렬 알고리즘을 pseudo code, average time complexity, worst time complexity, space complexity와 함께 설명하세요.

배열 : 6 0 4 5 1 3 8 2

정렬 알고리즘

1. Bubble sorting

버블 정렬은 인전 숫자를 2개 비교하여 작은 숫자를 앞으로 큰 숫자를 뒤로 보낸다.
이 정렬을 한 번 거칠때마다 n번째로 큰 수를 구할 수 있다.

• pseudo code

for i from n-1 to 1 do
    bChanged = 0; //교환이 발생하지 않음
    for j from 0 to i-1 do
    	if list[j] > list[j+1] then
        swap list[j] with list[j+1]
        bChanged = 1; //교환이 발생
   if !bChanged then break; 
       

• average time complexity
  O(n^2)
  n번의 pass동안 n개를 swap하므로 시간 복잡도는 O(n^2)이다.

• worst time complexity
  O(n^2)
  최악의 경우에도 n번의 pass동안 n개를 swap하므로 시간 복잡도는 O(n^2)이다.

• space complexity
  O(1)
  항상 2개의 요소만 비교하므로 constant하다.

2. Selection sorting

n번째자리에 n번째로 작은 숫자를 찾아서 swap하여 sorting합니다.

• pseudo code

    for i from 0 to n-2 
        least = i //0번째 인덱스에 제일 작은 값을 넣는다.
        for j from i+1 to n-1 //두번째부터 끝까지 
            if list[j] < list[least] // 더 작은 값을
                least = j  //j번째에 넣는다. 
        swap list[i] with list[least] //i와 j를 swap 한다.

• average time complexity
  O(n^2)
  n번의 pass동안 n개의 원소를 비교하므로 시간 복잡도는 O(n^2)이다.

• worst time complexity
  O(n^2)
  최악의 경우에도 n번의 pass동안 n개를 비교하므로 시간 복잡도는 O(n^2)이다.

• space complexity
  O(1)
  항상 1개의 요소만 뽑아오므로 constant하다.

3. Insertion sorting

n번째 있는 수를 n번 비교하여 작은 숫자를 앞쪽에 삽입하는 방식입니다.

• pseudo code

   for i from 1 to n-1 //두번째부터 n-1번째까지 
        key = list[i]  //키값을 i번째의 요소로 두고
		for j from i-1 to 0
            if f(list[j], key) <= 0 // list[j]가 key보다 작으면
                break;
            list[j+1] = list[j] // 아니라면 다음으로
        list[j+1] = key        //key값을 j+1번째에 넣기

• average time complexity
  O(n^2)
  n번의 pass동안 앞에 있는 n개의 원소를 비교하므로 시간 복잡도는 O(n^2)이다.

• worst time complexity
  O(n^2)
  최악의 경우에도 n번의 pass동안 앞에 있는 n개의 원소를 비교하므로 시간 복잡도는 O(n^2)이다.

• space complexity
  O(1)
  항상 1개씩 비교하므로 constant하다.

4. Quick sorting

평균적으로 가장 빠른 정렬 방법이다.
분할 정복법을 사용한다.
리스트를 pivot을 기준으로 2개의 부분 리스트로 비균등 분할하고 각각의 부분 리스트를 다시 quick 정렬하는 recursion을 사용한다.

피벗보다 작은 건 앞으로 큰 건 뒤로하는 것을 리스트의 크기가 0이나 1이될 때까지 반복

나눠질 때마다 피벗을 새로 정한다.

• pseudo code

partition(list, left, right)
    pivot = list[left] //제일 왼쪽 요소를 pivot으로
    low = left + 1  //왼쪽 바로 옆
    high = right //제일 높은게 오른쪽
    
    while low < high: //low랑 high가 역전되지 않을때까지 반복
    	while low <= right && list [low] < pivot
        	low++ //피벗보다 큰 값이 나올때까지 low증가
        while high >= left && list[high] > pivot
        	--high //피벗보다 작은 값 나올때까지 high 감소
            
        if low < high //역전 안됐다?
        	swap list[low], list[high] //서로 바꾸기
    return high
          
quick sort(list, left, right)
	int q // 피벗 정하기
	if left < right // 종결조건 왼쪽이 오른쪽보다 작을때 , 오름차순 정렬되면
    	q = partition (list, left, right) //파티션 만들기
        quick_sort(list, left, q - 1) //왼쪽 돌리기
        quick_sort(list, q + 1, right) //오른쪽 돌리기
    	

• average time complexity
  O(nlogn)
  n개를 log 스케일로 가져가므로 nlogn의 시간 복잡도를 가진다.

• worst time complexity
  O(n^2)
  계속 최소값이 left일 때는 n번만큼 해야하므로 O(n^2)가 된다.

• space complexity
  O(logn)
  한번에 logn개를 비교하므로 O(logn)이 된다.

5. Merge sorting

병합 정렬은 리스트를 두개의 부분 리스트로 분할하고 각각 정렬한다.
그리고 부분 리스트를 합해서 전체 시리스트를 정렬한다.
두개로 나누고 계속 나눠서 2개까지 나눠질떄까지 recursion을 하고
종결조건으로 left < right일 때를 준다.

• pseudo code

merge(list, left, mid, last)
	i <- left; //맨끝
    e1 <- mid; //미드
    j <- mid+1; //미드 옆
    e2 <- right; //맨 오른쪽
    sorted[]; //정렬된 거 담을 배열
    k <- 0;
    while i <= e1 && j <= e2 do //서로 범위 벗어나지 않을때
    	if(list[i] < list[j]) //작은 걸 sorted에 저장
 		then sorted[k++] <- list[i++]; // sorted[k++]에 list[i]저장하고 증가
 		else
 		sorted[k++] <- list[j++];// sorted[k++]에 list[j]저장하고 증가

merge sort (list, left, right)
if left < right //종결조건
	mid = (left + right) / 2 // 중간을 정하기
    merge_sort(list, left, mid); // 왼쪽의 미드를 구하기
    merge_sort(list, mid+1, right); //오른쪽의 미드를 구하기
    merge(list, left, mid, right); // 

• average time complexity
  O(nlogn)
  n개를 log 스케일로 가져가므로 nlogn의 시간 복잡도를 가진다.

• worst time complexity
  O(nlogn)
  최악인 경우에도 n개를 log 스케일로 가져가므로 nlogn의 시간 복잡도를 가진다.

• space complexity
  O(n)
  한번에 recursion을 통해 n개를 다룬다.

6. Heap sorting

Heap sorting은 힙 자료구조를 써서 정렬하는 알고리즘이다.
배열을 최대힙이나 최소힙으로 구성하고 루트를 마지막 요소와 교환한다.
힙크기를 감소시키고 다시 힙을 재구성
반복해서 전체 배열을 정렬한다.

• pseudo code

heapSort(arr)
    n = length(arr)

    for i from n / 2 - 1 to 0
        heapify(arr, n, i)

    for i from n - 1 to 0
        swap arr[0] and arr[i]
        heapify(arr, i, 0)

• average time complexity
  O(nlogn)
  n개를 트리대로 log 스케일로 가져가므로 nlogn의 시간 복잡도를 가진다.

• worst time complexity
  O(nlogn)
  최악인 경우에도 n개를 log 스케일로 가져가므로 nlogn의 시간 복잡도를 가진다.

• space complexity
  O(1)
  한번에 하나만 가져가므로 constant하다.