알고리즘 정렬 시간복잡도 정리

  자료구조론의 관점에서 배울 때도 물론 시간복잡도라는 것을 공부하지만, 그렇게 피부로 와닿지는 않았던 것 같다. 오히려 이때는 코딩하는 시각에서 바라보지 않으니 그저 사람이 정리하기 편한 버블, 선택, 삽입 정렬을 선호했고 그중에서도 가장 쉬운 선택 정렬을 좋아했다. 그리고 객관식으로 공부하는 관점에서는 코드를 살펴보고 알고리즘을 완성시키는 수준 정도로만 공부를 했기 때문에 그렇게 정렬이 중요하다는 것을 피부로서는 확 와닿지 않았던 것 같다.

 

[국가직 2015년도 컴퓨터 일반]

출처: https://www.gosi.kr/cop/bbs/selectBoardArticle.do

 

문제에서는 내림차순 버블정렬의 알고리즘을 구현한 함수라고 하였다. y+1의 원소가 y보다 크기 때문에 자리를 바꾸는 것을 알 수 있다. 따라서 답은 ④번이 맞다. 정말 딱 여기까지!가 공부했던 범위였던 것 같다. 하지만 이제는 직접 알고리즘을 구현하고 완성을 해야 하고, 퀵 정렬이나 힙 정렬 같은 심화 알고리즘 또한 익혀야 하기 때문에 좀 더 많은 능력이 요구될 것 같다.

 

 

 

  여기서 최선의 버블정렬이나 삽입정렬의 경우에는 이미 정렬이 된 데이터가 들어왔기 때문에 가장 최상의 시나리오인 아무리 많이 걸려도 n번만큼만 돌리면 정렬이 끝날 수 있다. 그런데 반면으로 퀵 정렬의 경우 최악의 시나리오가 있다. 퀵 정렬이 이미 정렬돼 들어온 경우에는 오히려 더 많은 시간이 걸린다. 아마도 앞으로는 이런 알고리즘에 대해 공부할 것이다.