아무거나

Selection Sort [선택정렬] Worst case performance : O(n^2) Best case performance : O(n^2) Average case performance : O(n^2) Worst case space complexity : O(n) total, O(1) auxiliary 선택정렬은 퍼포먼스가 n squared 로 좋지 않다. 하지만 구현이 쉬워서 많은 사람들이 사용하고 있다. [ 예제 ] 아래 그림의 4 6 1 3 5 2 리스트를 1 2 3 4 5 6 으로 차례가 맞게 정렬하자. 선택정렬의 예시를 알아보자. 선택정렬은 하나의 공간이 필요하다 그것을 Minimum value라는 공간이라고 한다. 그러면 처음 아이템부터 끝까지 비교하면서 해당 리스트를 정렬해보자. ..

Bubble Sort [거품정렬] performance : O(n^2) space complexity : O(1) * 시간복잡도가 O(n^2) 이므로 느리지만 코드가 단순하기 때문에 자주 사용된다고 한다. 거품정렬은 원소의 이동하는 모습이 거품이 수명으로 올라오는듯한 모습과 비슷하므로 지어진 이름이다. 해당 정렬의 목표는 인접한 두개의 자료를 비교해서 차순에 맞게 교환하는 작업을 정렬이 완료 될 때까지 해준다. 자료수에 한 개를 뺄 만큼 Looping을 하면서 서로 인접한 아이템을 swapping해주는 방법으로 해당 리스트를 정렬할 것이다. 즉, 아래와 같이총 4개의 아이템이 있으므로 우리는 총 3번(=n-1) Looping을 할 것이다. ( 예제 리스트: 6 5 3 1 ) [Loop Count : 1,..