Algorithm/Sort
-
[Sort] Bubble SortAlgorithm/Sort 2020. 11. 11. 13:52
[Sort] Bubble Sort 매번 연속된 두개의 인덱스를 비교하여 조건에 맞게 위치를 바꾸는 정렬. Time Complexity O(N^2) Space Complexity O(N) FLOW 현재 인덱스 값과 바로 이전 인덱스 값을 비교한다. 이전 idx에 있는 원소가 더 크면 둘의 위치를 변경한다. 현재 idx가 더 크면, 다음 idx로 넘어가서 두개를 다시 비교한다. for(int i=0; i sorted flag를 사용하면 개선 가능하다. 중간에 한번이라도 원소의 교환이 일어나면 flag의 상태를 변경해준다. 바뀌지 않았으면, 교환이 일어나지 않은 정렬된 상태이다. => 만약 정렬된 상태의 배열이 들어오면 Θ(n)만에 수행 가능하다. for(int i=0; i