Sorting (5) 썸네일형 리스트형 [Sorting 05] Insert Sort의 개념 및 구현 들어가며 날이 엄청 춥다. 드디어 겨울이 오나보다. 오늘은 개념은 쉽지만 비효율적인 알고리즘 중에 하나인 'Insert Sort'에 대해 알아보자. 개념 및 특징 이미 정렬된 리스트를 앞에서 부터 값을 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다. in-place 알고리즘이다. 시간 복잡도: O(N2) 선택정렬이나 거품정렬에 비해서는 빠르다.* 알고리즘 앞에서부터 차례대로 이미 정렬된 리스트와 비교하여 자신의 위치를 찾아 삽입한다. 리스트의 모든 원소에 대해 위와 1과 같은 과정을 반복한다. 소스코드(C++) #include #include #include #include using namespace std; typedef vector::iterator IT; void insertSor.. [Sorting 04] Bubble Sort의 개념 및 구현 들어가며 이제 주요 정렬(sort) 알고리즘의 반정도 포스팅을 했다. 어떻게 이렇게 다양한 정렬 알고리즘들을 생각해냈는지 그저 신기할 따름이다. 그간 알고리즘들이 머릿 속에서 정리가 안된 채 널부러져 있는 느낌이었는데 블로그 포스팅을 하면서 점점 정리가 되는 기분이 들어서 좋다. 오늘은 쉬운 정렬 알고리즘 중에 하나인 'Bubble Sort'에 대해 알아보자. 개념 및 특징 비교횟수: O(N2) 자리 교환 횟수 최선의 경우 - 이미 정렬이 된 경우 - 한번도 바꾸지 않아도 된다. - O(1) 최악의 경우 - 꺼꾸로 정렬이 된 경우 - O(N2) 알고리즘 인접한 두 수를 비교하여 큰 수를 뒤로 보낸다. 한번 순회할 때마다 비교하는 수가 하나씩 줄이면서, 정렬이 완료될 때까지 1의 과정을 반복한다. 소스코드.. [Sorting 03] Merge Sort의 개념 및 구현 들어가며 복잡한 정렬 알고리즘 중에서 가장 간단하다는 합병정렬(merge sort)에 대해 포스팅해 볼 것이다. 알고리즘을 막 공부하기 시작했을 때, merge sort를 구현하다가 막혀 며칠을 끙끙댔던 기억이 있다. 이제 그 때보다는 실력이 조금 나아졌으리라 기대하면서 포스팅을 시작해본다. 개념 및 특징 존 폰 노이만이 1945년에 개발했다. 분할정복(divide and conquer) 알고리즘 중 하나이다. 결과를 임시 배열에 저장했다가 다시 복사하는 과정이 발생하므로, 추가적인 메모리 공간도 요구되고 배열 복사에 시간이 소요된다. 최악 시간 복잡도: O(NlogN) 최선 시간 복잡도: O(NlogN) 평균 시간 복잡도: O(NlogN) 알고리즘 리스트의 길이가 1 이하면 이미 정렬된 것으로 본다. .. [Sorting 02] Selection Sort의 개념 및 구현 들어가며 일기를 쓰는 것과 블로그 포스팅을 하는 것은 정말 꾸준히 하기 힘든 것 같다. 공대생은, 특히나 컴공생은 고학년이 될 수록 한국어가 어려워지는 신기한 현상을 겪게 되기 마련이고 따라서 뭔가를 말로 설명하거나 글로 적어내는 것은 더더욱 어려워지는 거 같다. 잘 아는 것과 잘 설명하는 것, 글로 잘 풀어내는 것 전부 참으로 어려운 일이지만 많이 해보다보면 늘겠지 싶은 심정으로 오늘도 블로그 포스팅을 해본다. 오늘은 sorting 2번째 포스팅인데 sorting 중에서 가장 쉬운 편에 속하는 알고리즘인 'selection sort'에 대해 소개 하려고 한다. 개념 및 특징 제자리 정렬이다. 최악 시간 복잡도: O(N2) 최선 시간 복잡도: O(N2) 평균 시간 복잡도: O(N2) 알고리즘 주어진 리스.. [Sorting 01] Quick Sort의 개념 및 구현 들어가며 대학을 다니면서 알고리즘 과목을 수강하기도 했고 알고리즘 스터디도 했다. 혼자 온라인 저지 사이트에 들어가 쉬운 문제들을 빠르게 풀며, 또는 어려운 문제를 며칠씩 고민해가며 풀기도 했다. 그런데 놀랍게도, 내 머릿 속에 남아있는 알고리즘 지식은 거의 없다. '누군가 지금 당장 다익스트라를 구현해보시오.' 한다면 나는 분명 다익스트라를 익히 들어서 그 이름은 알고 있으나, 어떤 메커니즘을 가진 알고리즘인지 바로 떠올리지 못할 것이다. 이는 내 공부가 체계적이지 않았기 때문이라는 결론에 도달했다. 한 알고리즘을 배우고 이에 대한 다수의 문제를 풀어서 내껄로 만들었던 것이 아니라, 그때그때 필요한 알고리즘들을 찾아보고 그걸 써왔기 때문이다. 그래도 나름 열심히 배웠던 지식들이, 그저 머리를 스쳐지나가.. 이전 1 다음