맨날 insertion하고 selection하고 헷갈렸어서 insertion은 뭐였드라 하면서 코드를 봤더니만 이건 bubble이네요.
실패!
https://visualgo.net/bn/sorting 참고하세요.
사족(insert하고 select하고 다시 확인한 김에. ㅋㅋ)
물론 보통은 quick을 쓰면 해피하긴 하지만 다른 정렬수단을 배우는 이유는 아이디어를 배울 수 있다는 점외에 실무차원에서도 의미가 있어요.
selection은 제일 작은것, 혹은 제일 큰것을 찾아서 원하는 자리에 넣는 알고리즘이라 swap은 많아야 N번 일어납니다. 반면 비교는 O(N^2)번 일어나지요.
insertion은 이미 정렬된 배열에 값을 채워넣는 방식이라 swap은 O(N^2)번 일어나지만(linked list이면 swap도 O(N)번) 비교는 이미 정렬된 상태라 O(N log N) 번만 일어나지요.
그래서 비교가 느리고 swap이 빠른경우엔 insertion, 비교가 빠르고 swap이 느린경우엔 selection이 더 좋습니다. ( 극단적인 경우를 생각해보면 이게 quick보다 더 좋은걸 알 수 있을겁니다. )
즉 어떤 정렬알고리즘이 단순이 더 좋다 빠르다라고 말하는건 80점짜리 대답이고 데이터의 형태와 연산의 비용에 따라 최적의 알고리즘이 다르고 저런 예를 말할 수 있으면 최고입니다.
( 면접관의 습관이 남아있나봅니다. -_- )