[알고리즘] 기본 정렬 알고리즘

선택 정렬

최솟값을 찾아서 첫번 째 인덱스에 넣고, 그 이후 남은 값 중 최솟값을 찾아서 다시 다음 인덱스에 넣어 하나씩 정렬하는 방식

int main(void)
{
    int nums[10] = {50, 30, 90, 100, 20, 10, 40, 80, 60, 70};
    
    for (int i = 0; i < 10-1; ++i) {
        for (int j = i + 1; j < 10; ++j) {
            if (nums[i] > nums[j]) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
    }
    return 0;
}

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

버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

두 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환

void bubble_sort(int list[], int n){
  int i, j, temp;

  for(i=n-1; i>0; i--){
    // 0 ~ (i-1)까지 반복
    for(j=0; j<i; j++){
      // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
      if(list[j]<list[j+1]){
        temp = list[j];
        list[j] = list[j+1];
        list[j+1] = temp;
      }
    }
  }
}

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

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

삽입 정렬

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교, 제 위치를 찾아 삽입

// 삽입 정렬
void insertion_sort(int list[], int n){
  int i, j, key;

  // 인텍스 0은 이미 정렬된 것으로 볼 수 있다.
  for(i=1; i<n; i++){
    key = list[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

    // 현재 정렬된 배열은 i-1까지이므로 i-1번째부터 역순으로 조사한다.
    // j 값은 음수가 아니어야 되고
    // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+1번째로 이동
    for(j=i-1; j>=0 && list[j]>key; j--){
      list[j+1] = list[j]; // 레코드의 오른쪽으로 이동
    }

    list[j+1] = key;
  }
}
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

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

출처 : https://devuna.tistory.com/28
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html