[CS지식] 알고리즘

버블정렬

• 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하여 정렬

1회전을 수행하고 나면 , 가장 큰 원소가 맨 뒤로 이동하였고 , 2회전에서는 정렬에서 제외된다. 

2회전을 수행하고 나면, 끝에서 2번째 원소까지는 정렬에서 제외된다. 

 

시간복잡도 -> O(n^2)  

정렬이 안되어있던 2개의 원소를 비교하기 때문에, 

최선 ,평균, 최악의 경우 모두 시간복잡도가 동일하다 .

 

공간복잡도 -> O(n) 

주어진 배열 안에서 교환하기 때문에 

 

장점:

• 구현이 매우 간단하고  소스코드가 직관적
• 주어진 배열 안에서 정렬하므로, 다른 메모리 공간이 필요하지 않는다. =제자리정렬
• 안정정렬이다. 

단점: 

• 시간복잡도가 모두 O(n^2) 이므로 굉장히 비효율적이다. 
• 정렬돼있지않은 원소가 정렬됐을 때의 자리로 가기위해서 교환연산이 많이 일어난다.

 

선택정렬 

• 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 

시간복잡도 -> O(n^2) 

최선 ,평균, 최악의 경우 모두 시간복잡도가 동일하다 .

 

공간복잡도 -> O(n)

주어진 배열 안에서 교환하기 때문에 

 

장점:

• 버블정렬과 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만 , 실제로 교환하는 횟수는 적기때문에  많은 교환이 일어나야한은 자료상태에서 비교적 효율적이다.
• 배열 안에서 교환하는 방식이므로 다른 메모리 공간을 필요로 하지 않는다. 

 

단점: 

• 시간복잡도가 O(n^2)로 비효율적이다.
• 불안정정렬이다.