선택정렬 (Selection Sorting)

  • 선택정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬기법이다.
  • 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 O(N^2)의 시간 복잡도를 가진다.

#include <stdio.h>
#include <limits.h>
#define SIZE 1000

int a[SIZE];

int swap(int *a, int *b) {
    int temp = *a;
      *a = *b;
    *b = temp;
}


int main(void) {

    int n,min,index;
      for(int i = 0; i < n; i++) {
        scanf("%d",&a[i]);
    }
      for(int i = 0; i < n; i++){
        min = INT_MAX;
          for(int j = i; j < n; j++){
            if(min > a[j]) {
                min = a[j];
                  index = j;
            }
        }
      swap(&a[i],&a[index]);
    }

      return 0;
}

삽입 정렬

  • 삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번 이므로 O(N^2)의 시간복잡도를 가진다.
  • 두번째 원소부터 선택한 후 어디에 들어갈지 선정한다.
  • 즉, 들어갈 위치를 고르는 정렬방식이다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000
int a[SIZE];
int swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b
}
int main(void) {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < n - 1; i++) {
    int j = i;
    while (j >= 0 && a[j] > a[j + 1]) {
      swap(&a[j], &a[j + 1]);
      j--;
    }
  }
  system("pause");
  return 0;
}