Selection Sort

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.

5.

1~4의 과정을 N번 반복한다.

따라서 제일 큰 값은 맨뒤로가게 되고, 뒤에서부터 순차적으로 정렬되게 된다.

때로는 반대로 각 원소 중에서 작은것을 찾고 맨앞의 원소와 Swap하기도 한다.

Pseudo Code

SELECTION-SORT(A)
	while N>0
		for i <- 1 to N 
			if(A[i]>A[max]) 
				do max <- A[i]
		swap(A[N-1], A[max])

아래는 위의 코드를 바탕으로 C언어로 구현한 것이다.

C code

void selectionSort(int *A, int N){
	int max, i, temp;
	while(N>0){
		max = 0;
		/*Find max element*/
		for(i=1;i<N;i++){
			if(A[i]>A[max]) max = i;
		}
		/*swap(A[N-1], A[max])*/
		temp = A[N-1];
		A[N-1] = A[max];
		n--;
	}
}

Time Complexity

selectionSort의 시간복잡도는 각각 아래와 같다.

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

이때 Worst Case에서의 시간복잡도를 증명해보자.

Proof.

SELECTION-SORT(A)                  // Cost   times
	while N>0                        // C_1    n
		for i <- 1 to N                // C_2    sigma(i=0 to n, t)
			if(A[i]>A[max])              // C_3    sigma(i=0 to n, t-1)
				do max <- A[i]             // C_4    sigma(i=0 to n, t-1)
		swap(A[N-1], A[max])           // C_5    n-1

T(n) : The Sum of product of Cost and times of each line.

시간복잡도는 각 명령어가 실행될 때의 cost와 시간을 곱한것과 같다.
따라서 Worst Case에서 시간복잡도를 아래와 같이 나타낼 수 있다.

At Worst Case :

T(n) = C_1n+C_2 \sum_{i=0}^{n}t+C_3 \sum_{i=0}^{n}{(t_i-1)}+C_4 \sum_{i=0}^{n}{(t_i-1)}+C_5(n-1)

t_i = i \space\space for \space\space i = 1, 2,3,...,n

\sum_{i=1}^{n}i =\frac{n(n+1)}{2}, \space\space\space\space\space \sum_{i=1}^{n}(i-1) =\frac{n(n-1)}{2}\space

T(n) = C_1n+C_2\frac{n(n+1)}{2}+C_3\frac{n(n-1)}{2}+C_4\frac{n(n-1)}{2}+C_5(n-1)\\

= (\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5

T(n) = O((\frac{C_2}{2}+\frac{C_3}{2}+\frac{C_3}{2})n^2+(C_1+\frac{C_2}{2}-\frac{C_3}{2}-\frac{C_4}{2}+C_5)n-C5) \\=O(n^2)

만개의 숫자를 input.txt 입력받아 정렬하는 C code

https://github.com/ho4607/Algorithm/blob/master/SortingAlgorithm/selectionSort/selectionSort.c

github.com

#include <stdio.h>
#include <stdlib.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable :4996)
#define max_len 10000
// #include <ctype.h>

void main (){
	int dataBox[max_len];
	int max,temp,index,i,n,E;
	
	E = 0;
 	//file input
    FILE* fin;
    fin = fopen("input.txt","r");
    if (fin == NULL) { 
        printf("Fail to read file. \n\nCheck if the \"input.txt\" file exists in the directory.\n\n");
        E = 1;
    }
    for(i=0; i<max_len ;i++){  
   		fscanf(fin,"%d",&dataBox[i]);
	}
	fclose(fin);

	
	//Selection Sort
	n = max_len;
    while(n>0){
    	max = 0;
		for(index = 1; index<n; index++){
			if(dataBox[index]>dataBox[max])
				max = index;
		}
		temp = dataBox[n-1];
		dataBox[n-1] = dataBox[max];
		dataBox[max] = temp;
		n--;
	}
	
	//Check if there is a valid value inside the array and display it in the console. 
//	for(i=0; i<max_len; i++){
//		printf("%d ",dataBox[i]);
//	}
//	
	if (dataBox[0] < dataBox[max_len-1]&& E==0) { 
        printf("Sorting is complete.\nOpen the output file to check the results.  \n\n");
    }
	//file output
    FILE* fout;
	fout = fopen("output.txt", "w+");
    for(i=0; i<max_len; i++){   
   		fprintf(fout,"%d ",dataBox[i]);
	}
	fclose(fout);
}

이전으로 돌아가기

Algorithm

메인으로 돌아가기

Best Case : \Omega(n^2)

Average Case : \Theta(n^2)

Worst Case : O(n^2)

우리말로 선택 정렬이라고 하는 Selection Sort 알고리즘은 max값을 갖고 하나하나 비교해나가는 알고리즘이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1.

첫번째 원소부터 N번째 원소를 max값과 비교한다.

2.

이때 max값 보다 큰 값이 나타나면, 나타난 값으로 max값을 업데이트 한다.

3.

N번째까지 비교한 후, 검사한 맨 뒤의 값과 max값을 Swap한다.

4.

N의 크기를 1킨 줄인다.