Bubble Sort(버블 정렬)
버블정렬은 배열에서 2개의 인덱스를 선택하고 비교한다.(오름차순 가정)
왼쪽이 오른쪽보다 크면 교환한다.
오른쪽으로 한칸 이동해서 프로세스를 반복한다.
아래 예시로 이해해보자.
5는 2보다 크므로 서로 swap
이번에는 한칸 오른쪽으로 이동해서 5와 6을 비교한다. 왼<오 이므로 swap 하지 않는다.
다시 오른쪽으로 한 칸 이동해서 6과 3을 비교한다. 6>3 이므로 swap한다.
똑같은 방식으로 6과 1을 비교하고 swap, 6과 4를 비교하여 swap 하면 아래와 같이 버블 사이클 1회가 완료된다.
나머지를 정렬하려면 다시 처음부터 비교해서 버블정렬을 해주어야한다.
- 버블정렬은 배열의 N-1 의 원소들을 하나하나 비교해야하고 사이클마다 계속 비교하고 반복하므로 비효율적인 알고리즘이다.
- 최악의 경우 모든 원소를 교환해야하므로 시간 복잡도가 O(n^2)이다.
Selection Sort(선택 정렬)
선택 정렬은 전체 원소 중 가장 작은 원소의 위치를 "변수"에 저장한다.
가장 작은 원소 변수를 Min이라고 하자.
배열의 첫번째 원소의 위치를 Min에 저장한다.
만약 배열을 돌때 첫번째 원소 즉 Min보다 작은 값이 있다면 그 값의 위치를 다시 Min 변수에 저장한다.
이 과정을 계속 반복해 배열 내에서 가장 작은 숫자가 어디에 있는지 알아냈다. 이제 가장 작은 값을 배열의 맨 앞으로 swap 해준다.
1은 배열 내에서 가장 작은 값이므로 이미 정렬이 완료된 상태이다. 즉 다음 사이클을 시작할 때는 두번째 원소부터 시작한다. 이 과정을 계속 반복한다.
-
선택 정렬의 시간 복잡도: 버블 정렬과 비슷하게 교환, 비교하지만 사이클을 반복할 때마다 한번의 교환만 하면 돼서 버블정렬보단 효율적이다.
-
하지만 버블정렬과 같은 O(n^2) 복잡도를 가지고 있다.
<선택 정렬 구현 코드 c++>
#include<iostream>
#include<vector>
#include<queue>
#include <stack>
#include<algorithm>
#include<limits.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int i,j,min,index,temp;
vector<int> v={1,10,5,8,7,6,4,3,2,9};
for(int i=0;i<10;i++){
min=i;
for(j=i+1;j<10;j++){
if(v[min]>v[j]){
min=j;
}
temp=v[i];
v[i]=v[min];
v[min]=temp;
}
}
for(int i=0; i<v.size();i++){
cout<<v[i]<<" ";
}
cout<<endl;
return 0;
}