달력

112018  이전 다음

  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  •  

'sort'에 해당되는 글 2건

  1. 2011.03.13 [Algorithm]merge sort
  2. 2011.02.28 [Algorithm] Heap sort
merge sort의 기본 개념은 아래 그림과 같습니다.
사용자 삽입 이미지


정렬되지 않은 데이타가 들어오면 쪼갤수 없을때까지 쪼갠다음에 합치면서 정렬을 해나가는 알고리즘입니다.
대부분 예제 소스에는 재귀함수로 merge sort를 구현했는데요.  재귀함수로 안해도 되지않을까.....
라는 생각이 시작이었습니다.

쪼갤수 없을때까지 쪼개는과정이 불필요하다는 생각이 들었고, 그래서 제가 구현한 소스에는
처음부터 끝까지 돌면서
처음에는 두개씩 정렬, 그 다음에는 네개, 그 다음에는 8개.
이런식으로 정렬을 수행합니다.  재귀함수를 안쓰다보니 추가 메모리가 필요하네요;;(안쓰고도 가능한게 있으면 알려주세요)
아래는 구현한 소스입니다.


Posted by 오산돌구


Heap sort란 Heap 자료구조를 이용해서 sort하는 방법입니다.

우선 Heap에 대해 알아야겠죠?
http://dol9.tistory.com/129  전에 포스팅한게 있네요 : )
root에는 max값 혹은, min값이 있습니다.

정렬이 안된 데이타를 heap 구조로 만들고, root의 값 하나꺼내고 heap구조 재정렬하고
root의 값 하나꺼내고 정렬하고, 이를 반복하면 정렬된 데이타가 생성됩니다.


단순한 방법이네요;;;

아래는 지금 두줄 설명한것을 코딩한것입니다. 
생각한것을 막힘없이 구현할수 있도록 많이 짜보고 피드백 받고 수정하는 일련의 과정을 반복해야겠지요...



실용주의 개발자를 향해 부단히 노력해야겠습니다.


Posted by 오산돌구