[C++] Lab2 - Sorting Algorithm

Bubble sort

• Time complexity : O(n^2)
  1. First pass
  • Compare two elements
  • Swap descending/ascending order until the last element
  • The Lagest value has bubbled up to the rightmost pos
    1. Second pass
  • Compare two elements
  • Swap until second-to-last element
    1. Continue swapping
• Pros : Easy to Code
• Cons : O(n^2)

for (int i = 0;i<size-1;i++)
	for(int j = 0;j<size-1-i;j++)
	{
		if (arr[j]>arr[j+1]) {
			swap(arr[j], arr[j+1]);
		}
	}
	
	void recursive_bubble(int* arr, int size) {
		if (size>1){
			for (int j = 0;j<size-1;j++){
				if(arr[j]>arr[j+1]){
					swap(arr[j], arr[j+1]);
				}
			}
			recursive_bubble(arr, size-1); // Assume that last element is sorted
		}
	}

Insertion sort

• Time complexity : O(n^2)
  1. Start from idx=1 (second element from left)
  • Compare the indexes before current index
  • Insert the target in the appropriate location
    1. Start from index=2, continue
• Pros : Could swap less times than bubble, very fast when nearly sorted
• Cons : Worst case have O(n^2)

for(int i = 1;i<size;i++){
	int target = arr[i];
	int j = i-1;
	while(j>=0){
		if (arr[j]<=target) break;
		else {
		array[j+1]=array[j]; //copies the one before
		j--;
		}
	}
	array[j+1] = target; //put it
	
	void recursive_insert(int*arr, int size) {
		if(size>1){
			recursive_insert(arr, size-1); // after this, 1~last-1 is sorted
			int j = size-2; //start from last-1
			int temp = arr[size-1]; //last index
			while (1) {
				if (j<0 || arr[j]<=temp) break; // j is the right place for temp to get in
				arr[j+1] = arr[j]; //move
				j--;
			}
			arr[j+1] = temp; //move temp
		}
	}

• 항상 자신의 앞의 정렬된 idx들을 —를 통해 순차적으로 iterate하는데, 할 때마다 swap해서 공간 마련해두는거 잊지 않기.

Selection sort

• Time complexity : O(n^2)
  1. Start from idx=0,
  • Swap the minimum value in the remaining list
    1. Continue
• Pros : A few swap
• Cons : A lot of compare

for (int i =0;i<size-1;i++)
{
	int min = array[i];
	int min_idx = i;
	for(int j =i+1;j<size;j++) {
		if (array[j]<min) {
			min = array[j];
			min_idx = j;
		}
	}
	swap(array[i], array[min_idx]);
}

Complete Binary Tree

• Binary tree : each parent node has at most two children
• Complete binary tree :
  • All levels except last are completely filled.
  • Nodes in the last level are filled from left to right

Heap

• Complete binary tree-based structure with heap property
• Heap property : (Max heap property) : parent node’s value ≥ child’s values

Heap sort

• Max-heapify

• In certain node i, checks the Left and right children node, exchange if child node is larger than root node, if both, exchange with the largest node. If exchange happened, recursively call max-heapify
• Build Max-heap : start from i= length(A)/2-1, i—, perform max_heapify() to build initial max heap
• Heap sort : First build max-heap → array[0] has the largest value → swap array[0] with array[-1], and max_heapify(0). repeat until all elements are sorted
• Max_heapify를 len(A)/2 -1부터 0까지 돌리고 마지막 idx부터 0까지 iterate하면서 마지막 idx 랑 0이랑 스왑하고 max_heapify(0) call
• 일단 l, r이 2idx+1, 2idx+2인데 저장해두고 (이후 valid한거 확인)
• largest, largestidx 정의. 각각 부모노드로 초기화
• l이랑 먼저 비교를 해서 l이 valid하고 arr[l]이 부모노드보다 크면 largest, idx에 l 넣어주기.
• r이랑도 비교하는데 largest랑 비교해서 r이 valid하고 크면 largest, idx에 r 넣어주기
• largestidx랑 부모노드 원래 idx랑 다르면 swap이 일어나야하므로 swap하고 largestidx에 대해서 max_heapify recursive call해주기

Merge sort

• Divide the array into halves until each sub-array has length 1
• Keep merging halves together in the correct order
  1. Keep dividing untill each sub-array has length 1
  2. Merge : Compare The first element of left and right array, iterate
• Pros : Nice time complexity O(nlogn)
• Cons : Additional memory required for storing divided segments

void merge_sort(int* array, int l, int r) {
	if (l<r) //until each segment has length 1
	{
		int q = (l+r)/2;
		merge_sort(array, l, q);
		merge_sort(array, q+1, r);
		merge(array, l, q, r);
	}
}
void merge(int* array, int p, int q, int r) {
	int n1 = q-p+1;
	int n2 = r-q;
	int L[n1];
	int R[n2];
	for (int i = 0;i<n1;i++) L[i] = array[p+i];
	for (int j = 0;j<n2;j++) R[j] = array[q+j+1];
	int i(0), j(0);
	for (int k = p, k<=r;k++){
		if (L[i]<=R[j]) A[k] = L[i];i++;
		else A[k]=R[j]; j++;
}

• 머지 소트가 recursive하게 반복되니 l<r 조건 넣어주기
• q= 둘의 반, 양쪽에 대해 recursive call 해주고 마지막에 merge
• mege는 p, q, r을 입력으로 받는데 p는 L의 첫원소 q는 L의 마지막, r은 R의 마지막원소니
• n1, n2 계산하고 초기화, 대입해주고
• i, j (2개의 포인터) 0으로 초기화하고 k=p~r까지 돌면서 비교하고 넣고 idx 증가. 한쪽만 다 쓴 경우 고려. 마지막 r까지 처리해줘야하는거 기억

Quick sort

• Select end element as a pivot, divide array with given pivot so that left<pivot, right>pivot

• Partition
  • i : marker for left
  • j : marker for right (iterate for whole array)
    1. Set pivot as last index, set i= start-1 iterate for j=p~r-1
    2. If jth element is smaller than x // which means must located be located in leftpart
  • i=i+1 (expand left)
  • exchange A[i] and A[j]
    1. Finally exchange last element with i+1 (end of left partition+1)
    2. return i+1
• Pros : Average, best time complexity is O(nlogn), no additional memory required
• Cons : not stable (Worst case, O(n^2)

void quick_sort(int* array, int l, int r) {
	int q;
	if (l<r){
		q=partition(array, l, r);
		quick_sort(array, l, q-1);
		quick_sort(array, q+1, r);
	}
}
int partition(int* array, int p, int r){
	int i = p-1;
	int pivot = array[r];
	for (int j = p;j<r;j++){
		if array[j]<=pivot {
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i+1], arr[r];
	return i+1;
}

• 0-size-1까지 일단 파티션을 일단 나눠
• 파티션은 마지막 애로 정하고, 왼쪽포인터는 l-1, 오른쪽은 l을 일단 가리켜
• 오른쪽 포인터의 값이 피벗보다 작거나 같다면 왼쪽에 있어야 하니 일단 왼쪽 포인터를 증가시키고
• 왼쪽 포인터와 오른쪽 포인터의 값을 스왑시켜
• 최종적으로 왼쪽포인터+1이 파티션의 위치가 되니 마지막값과 왼쪽 포인터+1의값을 스왑하고
• 왼쪽포인터+1의 값을 반환
• quick_sort가 recursive하게 로딩되니 l r 판별조건 만들어주고, 파티션은 이미 전체 array에 대해 정렬된 상태니 recursive 할 때 q는 뺴고 넣기.

Counting Sort

• Given small value of range of elements
  1. Find maximum value of the array, make counting array size of (max val + 1)
  2. Count each element and store it into counting array
  3. Calculate cumulative sum of counts
  4. Start from last element of original array, read counting array’s value → the value is index of sorted array

1. If the element is placed in sorted array, decrase the number in counting array by 1
   • Pros : O(n+k) where k is value range
   • Cons : if k is much larger than array size n, it becomes inefficient, Additional space memory to save counting array

void counting_sort(int* array, int size) {
	int max_val = array[0]; //scan max val
	for (int i =1;i<size;i++){
		if (arr[i]>max_val) {max_val = arr[i]}
	}
	int count[max_value+1] ={0};
	for (int i =0;i<size;i++) {
		count[arr[i]] +=1;
	}
	for(int i =1;i<max_value+1;i++) {
		count[i] +=count[i-1];
	}
	int sorted[size];
	for (int i=size-1;i>-1;i--) {
		sorted[count[arr[i]-1] = arr[i]; // -1 : if one exists : val of carray would be one
		count[arr[i]]-=1;
	}
	for(int i =0;i<size;i++){
		array[i] = sorted[i];
	}
}

• 최대 값 뽑아내기 → 해당 뽑아낸걸로 array만들기, iterate하면서 값의 갯수 세기 → cumulative sum (전항 + 현재항) → 원래 arr에서 iterate하면서 counting array의 값을 index로 재정렬하기. 사용헀으면 —해(중복 고려)

Stooge sort

1. Compare first and last value, swap if needed
2. Recursively sort former 2/3 of array
3. Recursively sort latter 2/3 of array
4. Recursively sort former 2/3 of array

void stooge_sort(int* array, int l, int r) {
	if (l<r){ 
		if (array[l]>array[r]) {
		 swap(array[l], array[r]);
		} //swap first and last element
		if (r-l+1 >2) { //Length of array is bigger than 3(1/3 divisible)
			int q = (r-l+1)/3 ; // one third
			stooge_sort(array, l, r+q);
			stooge_sort(array, l+q, r);
			stooge_sort(array, l, r+q); //sort former-latter-former 2/3 of array
		}
	}
}