sorting

1. Insertion sorting (O(n^2))

zzzzzzzzzz

2. Selection sort(O(n^2))

http://luckyyowu.tistory.com/127

배열의 0번쨰 요소부터 끝까지

0 1~N 까지 요소와 비교하면서 최솟값을 넣느다

i i+1~N까지랑 비교하면서 최솟(댓)값으로 하나씩 채워나감

3. Heap Sort

http://proneer.tistory.com/entry/Sort-%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-Sort

<연습문제>

Your program reads its inputs from the input file “heapsort.in”, and outputs its output to the output file “heapsort.out”. In heapsort.in, the first line includes a list containing the elements to be sorted. In heapsort.out, you have to print out the structure of the binary heap used in the heapsort using inorder(I) traversal and preorder(P) traversal whenever the binary heap is changed. Finally, the last line outputs a sorted list of elements. Note that you have to use letter I, P, and O to denote inorder traversal, preorder traversal, and output, respectively.

===========================================================

heapsort.in.

4 7 5 8

=========================================================

heapsort.out

I 4

P 4

I 7 4

P 4 7

I 7 4 5

P 4 7 5

I 8 7 4 5

P 4 7 8 5

I 7 5 8

P 5 7 8

I 8 7

P 7 8

I 8

P 8

O 4 5 7 8

#include
char _arr[1000],temp,cnt;
void inorder(int *arr, int x);
void preorder(int *arr, int x);
void insert(int *arr, int x);
void _sort(int *arr);
int main(){
	int temp,n,in[10000],len=1,sort[10000],loc=0;
	freopen("heapsort.in", "rb", stdin);
	freopen("heapsort.out", "w", stdout);
	while (1){
		temp = scanf("%d", &n);
		if (temp == -1)
			break;
		else{
			in[len++] = n;
			insert(in, len-1);
		}
		cnt = 0;
		inorder(in,1);
		printf("I ");
		for (int j = 0; j < len-1; j++)
			printf("%d ", _arr[j]);
		printf("\n");
		cnt = 0;
		preorder(in,1);
		printf("P ");
		for (int j = 0; j < len-1; j++)
			printf("%d ", _arr[j]);
		printf("\n");
	}
	for (int j = len - 1; j > 0; j--){
		sort[loc++] = in[1];
		in[1] = in[j];
		in[j] = -1;
		if (j == 1)break;
		_sort(in);
		printf("I ");
		cnt = 0;
		inorder(in,1);
		for (int l = 0; l < cnt; l++)
			printf("%d ", _arr[l]);
		printf("\nP ");
		cnt = 0;
		preorder(in,1);
		for (int l = 0; l < cnt; l++)
			printf("%d ", _arr[l]);
		printf("\n");
	}
	printf("O ");
	for (int j = 0; j < len - 1; j++)
		printf("%d ", sort[j]);
}
void _sort(int *arr)
{
	int temp, i = 1, j;
	while (1)
	{
		if (arr[i * 2] < 0 )break;
		if (arr[i * 2 + 1] < 0)
			j = i * 2;
		else if (arr[i * 2] < arr[i * 2 + 1]){
			j = i * 2;
		}
		else
			j = i * 2+1;
		if (arr[i]>arr[j])
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i = j;
		}
		else
			break;
	}
}
void insert(int *arr, int x){
	while (x != 1){
		if (arr[x / 2] > arr[x]){
			temp = arr[x];
			arr[x] = arr[x / 2];
			arr[x / 2] = temp;
		}
		else
			break;
	}
}
void inorder(int *arr,int x){
	if (arr[x]>0){
		inorder(arr,2*x);
		_arr[cnt++] = arr[x];
		inorder(arr,2*x+1);
	}
}
void preorder(int *arr, int x){
	if (arr[x] > 0){
		_arr[cnt++] = arr[x];
		preorder(arr, 2 * x);
		preorder(arr, 2 * x + 1);
	}
}

4.merge sort(O(nlogn))

http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort

1. start with the unsorted list I of n input items

2. Break Z into two halves Z1 and Z2, having [n/2] and items

3. Sort I1 recursively, yielding the sorted list s1

4. sort I2 recursively, yielding the sorted list s2

5. Merge s1 and s2 into a sorted list S=>O(n)

W(n)=2*w(n/2)+n

W(1)=0

Merge algorithm

1.Let q1 and q2 be two sorted queues.

2.while (neither q1 nor q2 is empty){

item1=q1.front();

item2=q2.front();

move the smaller of item1 and item2 from its present queue to the end of q

}

3. concatenate the remaining non-empty queue(q1 or q2) to the end of q

Complexity of Mergesort

Recurrence relation

W(n)=2W(n/2)+n

W(1)=0

n=2^k

W(2^k)=2W(2^(k-1))+2^k

           =2(2W(2^(k-2)+2^(k-1))+2^k

           =4(W(2^(k-2))+2*2^k

           =2^k(W(2^(k-k))+k*2^k

           =k*2^k

W(n)=nlogn

 

5. quick sort

http://proneer.tistory.com/entry/Sort-%ED%80%B5-%EC%A0%95%EB%A0%ACQuick-Sort

** Quicksort on arrays

-the fastest known

Comparison-based sort for arrays

-(O(n^2) worst-case running time

-- O(nlogn) average-case running time

Ex)

6. Bucker sort(linear time sort)

simulation

https://www.cs.usfca.edu/~galles/visualization/BucketSort.html

-the number of items : n

-the range of keys : [0, q-1]

-time complexity : θ(q+n)

           * if q∈O(n), θ(q+n)= θ(n)

 

Ex) q=8, n=8

           Input : (6:a),(7:b),(3:c),(0:d),(3:e)--key,(1:f),(5:g),(0:h)

Queue:

** we need a pointer to find the end of a list in O(1)

Output : (0:d)(0:h)(1:f)(3:c)(3:e)(5:g)(6:a)(7:b)

O(q+n)

*Bucket sort is said to be “stable”.

-- A sort is stable, if items with equal keys come out in the same order in the output as they appeared in the input

7. comparison based sort