현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

정렬 질문

red10won의 이미지
글쓴이: red10won / 작성시간: 수, 2012/05/30 - 12:01오후

1,150,251
7,743,644
4,069,103
3,246,332
8,566,587
.
.
.
.
.
.
.
.
.

number.txt 파일에 저장된 7자리의 숫자 100만개를 정렬할려구 하는데
저 숫자들이 겹치지 않는다면
가장 빠른 정렬 방식이 어떤게 좋을가요?

arry[9999999] 만들어서,,

arry[1150251] = {1}
arry[7743644] = {1}
arry[4069103] = {1}
arry[3246332] = {1}
arry[8566587] = {1}
arry[1150251] = {1}
.
.
.
.
.

저장하고 {1}인 것의 배열만 output.txt에 담는게 가장 빠른가요?
저런식의 정렬 방식을 머라고 부르나요?

저런식으로 되면 정말 Time complexity가 O(n)이 되나요?

Forums: 
프로그래밍 QnA
익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 수, 2012/05/30 - 12:33오후

O(n)에서 n은 데이터 갯수입니다..

자리수가 정해진 정수라면 radix sorting도 좋은 방법입니다.

정상인의 이미지

글쓴이: 정상인 / 작성시간: 수, 2012/05/30 - 1:03오후

윗 분이 말씀해주신 Radix Sorting이 정확한 바운드가 기억나진 않습니다만 아마 O(kn)이었을 겁니다.이 경우 k값(자릿수)이 고정이므로 O(n)바운드라고 볼 수 있습니다.
숫자 갯수만큼 변수를 할당한 후에 거기서 1인 배열만 output.txt에 담으시는 경우 0부터 9999999까지를 전부 서치하셔야 하므로 100만개가 아닌 O~9999999까지,즉 1000만번의 연산이 필요합니다. 따라서 O(n)은 아닙니다. (n이 100만개이든 200만개이든 무조건 천만번 돌아야 합니다.)
따라서 이 경우엔 Radix Sort를 쓰는 게 맞습니다. 하는 요령은 위키같은데에 나와있습니다.

planetarium의 이미지

글쓴이: planetarium / 작성시간: 수, 2012/05/30 - 9:30오후

그런데 저런 정렬 방법이 O(n)이 아니면 뭔가요? 배열 읽기 회수가 상수값이라도 봐도 결국 O(n)이고 (상수가 커서 실용성이 없더라도)
n에 관련있는 값이라도 봐도 어쨌든 O(n)+O(n) => O(n) 이 되는거 아닌가 싶은데... 별 자신은 없고 그냥 궁금하네요.

정상인의 이미지

글쓴이: 정상인 / 작성시간: 수, 2012/05/30 - 11:33오후

네, 제 실수가 있었던 것 같습니다...
데이터를 배열에 저장하는 단계를 O(n)으로 가정할 경우 기존의 방법도 O(n) 바운드로 해석이 가능할 것 같습니다. 어쩌다가 그랬는진 모르겠는데 이 부분을 다른 값으로 생각하고 답을 적었습니다.
혼란을 일으켜 죄송합니다.

red10won의 이미지

글쓴이: red10won / 작성시간: 수, 2012/05/30 - 1:00오후

제가 잘못생각했네요 ㅎ

무식이 탄로나네요 ㅋㅋ
공부좀 더 해야겠습니다 ㅎ

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 수, 2012/05/30 - 4:39오후

한번만 정렬하실꺼면..

정렬기능이있는 에디터나.. 엑셀..등으로 읽어 정렬하면

제일빠르죠^^

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 수, 2012/05/30 - 5:11오후

존 벤틀리가 쓴 "생각하는 프로그래밍"(원제 "Programming Pearls")의 첫 장에 같은 문제가 나옵니다.

여기서 제시한 방법 중에 비트맵이 있는데, 원리는 처음 쓰신 내용과 같습니다. 다만, 배열의 각 요소가 비트라는 점이 다르죠.
예를 들어 한 자리 숫자만 정렬할 때 입력이 1, 3, 5라고 한다면 아래와 같이 각 1, 3, 5번째 비트가 1이 되는 겁니다.

0101010000

모든 입력에 대해 비트맵을 완성하면 순서대로 읽어나가면서 값이 1인 비트의 위치만 출력하면 정렬된 결과를 얻을 수 있습니다.
Time complexity는 입력에서 n개를 읽고 출력에서 n 비트를 읽으니 O(n)이 되고요.

물론 이 방법은 모든 입력값이 유일하다는 전제하에 사용할 수 있겠죠.

lucidite의 이미지

글쓴이: lucidite / 작성시간: 수, 2012/05/30 - 11:02오후

위에서도 나온 내용이지만 O(n)이 되지 않는 것 아닐까요.
n은 정렬하고자 하는 데이터 집합의 크기니까요.

말씀해 주신 것처럼 비트맵을 완성한 후 '순서대로' 읽어나가면
time complexity는 비트맵의 사이즈에 의해 결정되지 않을까 싶네요.
정렬하고자 하는 데이터 집합의 크기가 아니라...

이와 같은 정렬 방식은 정렬 대상이 일정 범위 내의 정수이고
밀도가 매우 높은 데이터(좁은 범위 내에 많은 데이터가 밀집한...)의 경우에 쓸 수 있지 않을까 싶군요.
이를테면 데이터 값의 범위보다 데이터 개수가 많은 경우라던가요.
(정수 외에도 유리수도 가산집합이므로 이론적으로 가능할 것 같긴 하지만 실제로는...음...)

그리고 입력값이 유일하지 않은 경우에는 중복 개수를 세는 방식으로 사용할 수 있지 싶습니다.
0/1과 같은 on/off가 아니라 counting으로^^

익명 사용자의 이미지

글쓴이: 익명 사용자 / 작성시간: 목, 2012/05/31 - 5:19오후

말씀하신 대로 비트맵을 읽을 경우에는 O(n)이 아니라 O(bitmap size)가 되겠군요. 제가 착각했습니다. ^^;

drinkme의 이미지

글쓴이: drinkme / 작성시간: 수, 2012/05/30 - 11:12오후

그거 고민할 시간에, 그냥 정렬하는게 싸요.

$ sort number.txt

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.