(정렬) 선택정렬 코드

시간 복잡도 : O(n^2)

pseudo code

input : 크기가 n인 배열 A
output : 정렬된 배열 A
for i = 0 to n-2{
  min = i
   for j = i+1 to n-1 {
      if(A[j]<A[min])
        min = j
      }
   A[i] <-> A[min]
}
return 배열 A

 

c 코드 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void SelectionSort(int* A,int n) {
	for (int i = 0; i < n - 1;i++) {
		int min = i;
		for (int j = i + 1; j < n; j++) {
			if (A[j] < A[min]) {
				min = j;
			}
			int tmp = A[i];
			A[i] = A[min];
			A[min] = tmp;
		}
	}
}

int main() {
	clock_t start, end;
	int numbers[600001] = { 0, };
	int num = 0;
	scanf_s("%d", &num);
	for (int i = 0; i < num; i++) {
		int tmp = rand() % 100 + 1;
		numbers[i] = tmp;
	}
	start = clock();
	SelectionSort(numbers, num);
	end = clock();
	printf("총 소요시간 : %.3f\n", (float)(end - start) / CLOCKS_PER_SEC);
	system("pause");
	return 0;
}

실행시간

8개 : 0.000

100개 : 0.000

10,000개 : 0.131

60,000개 : 4.529

600,000개 : 452.249

1,000,000개 : 1256.739