[정렬 알고리즘] 선택정렬, 삽입정렬, 버블정렬 C++ 구현

선택 정렬, 삽입정렬, 버블정렬은 모두 최악의 경우 quadratic time에 수행되는 정렬이다.

 

 

 

1. 선택정렬

 

선택 정렬은, i (0~n-1)번째의 인덱스에 i부터 n-1까지 중 가장 작은 값을 넣는 작업을 반복하는 정렬입니다.

 

#include <iostream>
using namespace std;
int main() {

  int n;
  int data[100];
  
  cin >> n;
  
  for(int i = 0; i <n; i++){
    cin >> data[i];
  }
  
  for(int i = 0;i<n; i++){
    // i번째에 최솟값을 넣어라
    int inx = i; // inx = 최솟값
    
    // i번째 ~ 맨 끝까지의 값 중 최솟값 
    for(int j = i ; j <n; j++){
      if(data[inx] > data[j]){ // inx값이 최솟값이 아님
        inx = j;
      }
    }    
    
    // i인덱스랑 inx 인덱스 데이터 swap
    int temp;
    temp = data[i];
    data[i] = data[inx];
    data[inx] = temp;
  }
  
  // 출력
  for(int i = 0; i <n; i++){
    cout << data[i] << " ";
  }
  return 0;
}

 

 

 

---

 

 

2. 삽입정렬

삽입정렬의 경우, 최악의 경우에는 quadratic time에 수행되지만, 실제로는 입력의 개수가 작다면 O(nlogn) time에 수행되는 다른 정렬들보다 빠른 수행시간을 보입니다.

 

#include <iostream>
using namespace std;

int main() {

  
  int n, data[100];
  cin >> n;
  
  for(int i = 0; i <n; i++){
    cin >> data[i];
  }
  
  
  for(int i = 0; i <n ;i++){
    for(int j = i; j >=1 ; j--){
      
      if(data[j-1] > data[j]){// j : i ~ 1까지(j-1이랑 비교)
        int temp;
        temp = data[j-1];
        data[j-1] = data[j];
        data[j] = temp;
      }
      else break; // 더 크면 더이상 비교할 필요 x(앞은 정렬이 되어있으니까)
      
    }
  }
  
  for(int i = 0; i <n; i++){
    cout << data[i] << " ";
  }
  return 0;
}

 

 

---

 

3. 버블정렬

버블정렬은 인접한 두 값을 n-1번 ~~~ 1번 비교해서 작은 값을 앞으로 보내는 방식을 취한다.

#include <iostream>
using namespace std;

int main() {

  // 정렬 x | 정렬됨(큰 수) -> |를 점점 앞으로 보냄
  
  int n, data[100];
  cin >> n;
  
  for(int i = 0; i <n; i++)
  {
    cin >> data[i];
  }  

  for(int i = 0; i <n; i++){
    // n번 훑겠다!
    for(int j = 0; j<n-1; j++){
      if(data[j] > data[j+1]){
        int temp;
        temp = data[j];
        data[j] = data[j+1];
        data[j+1] = temp;
      }
    }
  }
  
  
  for(int i = 0; i <n; i++){
    cout << data[i] << " ";
  }
  return 0;
}