본문 바로가기

(탈퇴) Reuent's Post/Algorithms

Algorithm #1. Sort algorithm. - 1.1 정렬 알고리즘의 필요성, 그리고 알려진 알고리즘의 종류와 일반적 특성.


흠... 자료구조 포스팅을 먼저 한다는걸 잊고 알고리즘부터 준비했군요 -_-;;;; 정렬 알고리즘들의 포스팅이 끝난 다음엔
기초 자료구조부터 시작하죠.
- ... 포스트 제목을 정말 거창하게 지어버렸네요 -_-;; -

여튼. 이번 포스팅 주제는, Sort algorithm. 즉 정렬 알고리즘입니다.

어떤 작업을 하든지 우린 '정렬작업' 이라는걸 해야하는 경우가 많습니다.

사실 우리 주위엔 정보를 정렬하는 것이 필수적인 분야들이 많습니다. 가장 대표적인 예를 들자면 고객 관리 프로그램이겠죠.
특히 중, 고등학생들의 정보를 관리하는 학생 정보 관리 시스템이라던가.

자. 물론 자료 입력시 정렬을 해서 넣는 경우도 있겠죠. 하지만 우리가 프로그래밍을 할 땐, 우리의 고객이나 서버 채점기는
'정렬을 하지 않고 자료를 입력한다.' 는 가정 하에 시작해야 합니다. 만약 그렇지 않다면... 큰 사단이 나겠죠? -_-;;;

생각을 해 봅시다. 대한민국의 수많은 중. 고등학생들의 학생정보가 정렬 없이 너저분하게 널려있는 모습을. 그리고 그 안에서
우리의 선생님이 내 이름을 찾으려 낑낑대는 모습을.

눈물나겠죠? -_-;;;
- 사실 가장 좋은 방법은 위에서 이미 언급했듯이 정렬을 하면서 모든 자료를 넣는 겁니다만... -_- 쉽지 않겠죠. -

여튼. 이쯤 하면 정렬 알고리즘의 필요성은 충분히 아시리라 생각합니다.  물론 사족이었을지도 모르겠지만, 어쨌든 현대사회에서
정보 정렬의 필요성은 충분히 숙지하고 있어야 한다고 생각해 한번 더 다들 아실 내용을 이야기 해 봤습니다.

그럼 본격적으로 시작할까요.

기본적으로 정렬 알고리즘은 앞서 언급한 대로 정보 정렬의 필요성이 크게 심화됨에 따라 오랫동안 연구되어 왔고, 그에 따라
많은 종류의 알고리즘들이 등장했습니다.

한 알고리즘 A 가 소개되면 이를 더 빠르고 안정성있게 정렬하는 B가 등장하고, 또 이를 개선한 C가 등장하고. ....

그럼 지금까지 소개된 정렬 알고리즘의 종류들은 어떤 것들이 있을까요?  일단 간단한 것 부터 단순히 나열해 보죠.



  1. 선택 정렬 (Selection Sort)

  2. 삽입 정렬(Insertion Sort)

  3. 거품 정렬(Bubble Sort)

  4. 쉘 정렬(Shell Sort)

  5. 퀵 정렬(Quick Sort)

  6. 병합 정렬(Merge Sort)

  7. 기수 정렬(Radix Sort)

  8. 힙 정렬(Heap Sort)




가장 간단히 나열하자면 8개 정도로 줄일 수 있겠죠.

물론 이 중 가장 보편적인 상황에서 쓰이는 알고리즘은 Quick Sort 입니다. 일반적으로 속도도 빠르고, 구현도 간편하니까요.
- C언어 레퍼런스 함수로 qsort() 라는 것이 있습니다. 직접 구현할 필요가 없죠. -

하지만, 모든 상황에서 Quick Sort가 가장 빠르고, 정확한 대안이 되는 것은 아닙니다.

차후에 더 언급하겠지만, 메모리를 희생할 수만 있다면 Radix Sort 알고리즘 중에서도 '직접 기수 정렬(Straight Radix Sort)' 을
이용해 자료를 정렬하는 것이 더 빠른 경우가 있습니다.
- Radix Sort는 스택에 입력된 자료들을 비트열로 쪼갠 뒤에 비트를 가지고 정렬을 하므로, 입력 자료에 무관하게 같은 개수의
  자료라면 매우 빠른 정렬 결과를 산출할 수 있다고 알려져 있습니다. -

이처럼 상황에 따라서 선택해야 하는 알고리즘이 바뀔 수 있습니다.

프로그래밍 언어와 컴파일러는 프로그래머의 실수로 인해 빚어진 상황에 대해서는 전혀 책임을 지지 않습니다.

모든 상황에 대한 책임은 자료구조와 알고리즘을 선택한 프로그래머에게 있습니다.

잘못된 알고리즘을 사용해서 피본 경우는 모두 한번씩 있겠죠. 물론 저도 마찬가지구요.

프로그래밍을 할 땐 자료구조와 알고리즘의 이해도, 그리고 상황에 맞는 선택이 프로그램의 성능을 좌우합니다.

모두들 제 포스트를 통해서 - 그리고 다른 분들의 포스트를 통해서 - 함께 알고리즘들에 대해 고찰해보고, 한번 더 생각하는
계기를 갖게 되었으면 하면서 일단 이번 포스트를 마칩니다.

다음엔 위에서 언급한 - 그리고 아직 언급하지 않은 - 알고리즘들을 자세히 분석해 보고, 그 구현법에 대해 논하도록 하죠.

지금까지 읽어주셔서 대단히 감사합니다 -ㅁ-.