자바의 오름차순 정렬에는 여러 방법이 있다.
알고리즘 문제를 풀다보니 숫자를 오름차순 정렬해야 하는 일이 많았다.
알고리즘 문제 풀이의 특성상 숫자 정렬은 Arrays.sort() 혹은 Collections.sort() 등의 메소드를 사용할줄 아느냐를 물어보는게 아니기 때문에
직접 코드로 구현을 해보았다.
1.다음은 흔히들 알고있는 temp 변수를 이용한 방법이다.
int temp = 0;
for(int i = 0; i<n ; i++) {
for(int k = i ; k<n; k++) {
if(arr1[i] > arr1[k]) {
temp = arr1[i];
arr1[i] = arr1[k];
arr1[k] = temp;
}
}
}자신만만하게 문제를 풀고 제출하였으나!
맙소사! 시간초과가 나왔다!
원인은 정렬을 하는 이중for문에서 시간이 너무 사용되었기 때문이였다.
해당 정렬방법은 선택정렬(Selecetion Sort) 알고리즘의 구현방법으로, 시간복잡도가 O(n^2) 이다.
바깥loop가 n번 실행되며, 안쪽 loop는 현재 index 부터 n번 실행되어
전체 연산횟수는 n * (n-1) /2가 된다.
2.성공한 예제를 보니 Arrays.sort()를 사용한 예제가 보였다.
Arrays.sort(arr1); 
실행결과 정상적으로 정답이 나왔으며 속도차이는 기존 1982ms 에서 739ms로 절반이상 감소된것이 보인다.
어떤차이가 있는지 Arrays.sort() 메소드를 찾아서 들어가보았다.
퀵정렬에 대해선 정보처리기사를 공부하면서 본적이 있다.
평균 시간복잡도는 O(NlogN), 최악의 시간복잡도는 O(N^2)이다.
해당 정렬의 구현코드는 아래 블로그에서 자세히 설명이 되어있었다.
https://codingdog.tistory.com/entry/java%EC%9D%98-arrayssort-%EB%A9%94%EC%84%9C%EB%93%9C%EB%8A%94-%EC%96%B4%EB%96%A4-%EC%A0%95%EB%A0%AC%EC%9D%84-%EC%82%AC%EC%9A%A9%ED%95%A0%EA%B9%8C%EC%9A%94
3.Collections.sort()메소드는 어떨까?
MergeSort는 평균과 최악 시간복잡도가 모두 O(NlogN) 이라고 하며
TimeSort는 Insertion Sort와 Merge Sort를 합친 것이라고 한다.
기본적으로 Collections.sort()의 시간복잡도는 O(NlogN) 이라고 보는게 맞을것 같다.
알고리즘을 공부하다가 무의식적으로 작성한코드가 선택정렬이였음을 리뷰하는 계기가 되고
퀵정렬은 어쩌고, 버블정렬은 어쩌고.. 단순히 정보처리기사 자격증 취득을 위해 공부했던 내용인데
실제 자바객체에서는 어떻게 구현되어 있는지 찾아보고, 구글링을 하는 과정에서 '아 이게 이래서 필요한 거였구나.' 라는것을 직접 겪게 되었다.
