Q&A와 스터디
![[레벨:6]](http://old.lameproof.com/modules/point/icons/default/6.gif "포인트:3960point (61%), 레벨:6/30"){kind=icon}
마자마자200만개의 정수를 만개단위로 끊어서 200개의 파일을 만들고 (만개의 정수가 들어있는 파일을 200개를 생성하는거죠)
201번째의 파일에 생성된 200만개의 정수를 정렬하여 써넣어야 합니다.
정수는 랜덤하게 생성하고, 어떠한 정렬 알고리즘을 사용하던 최단시간을 끌어내야 합니다.
그래서 두가지 방법을 생각해봤는데,
처음 파일을 생성할때부터 만개단위로 퀵정렬을 해서
정렬된 만개의 정수를 200개의 파일에 쓴뒤 201번째 파일에 병합정렬을 하는 방법과,
(정렬된 데이터를 정렬할때는 병합정렬이 가장 빠르다고 알고있습니다)
처음부터 파일을 생성할때 정렬하지 않고 랜덤하게 생성해놓은다음
200만개의 정수를 한번에 퀵정렬로 정렬하여 파일에 쓰는 방법을 생각해 봤습니다.
제가 생각했을때는 처음 파일을 만들때부터 정렬하여 만든뒤 병합정렬로 정렬하여 201번째 파일에 쓰는 방법이 더 빠를거라 생각했는데,
오히려 200만개의 정수를 퀵정렬 한번하여 201번째 파일에 쓰는것이 더 빠르게 나오더군요.
그리고 정렬된 파일을 병합정렬로 201번째 파일에 쓰는것과
퀵정렬로 201번째 파일에 쓰는것을 비교해 보니, 병합정렬을 하는것보다 퀵정렬을 할때가 더 빠른경우도 자주 나타나던데 정렬된 데이터를 다시 정렬하여 넣을때
병합정렬이 가장 빠르다고 알고있던건 잘못 알고있던것인지, 아니면 그만큼 퀵정렬과 병합정렬의 차이가 크게 나지 않는것인지 궁금합니다.
요지는, 200만개의 랜덤한 정수를 만개단위로 끊어서 200개의 파일을 만든뒤 201번째 파일에 정렬해서 넣어야 한다면
어떻게 구현하는게 가장 빠를까요?
201번째의 파일에 생성된 200만개의 정수를 정렬하여 써넣어야 합니다.
정수는 랜덤하게 생성하고, 어떠한 정렬 알고리즘을 사용하던 최단시간을 끌어내야 합니다.
그래서 두가지 방법을 생각해봤는데,
처음 파일을 생성할때부터 만개단위로 퀵정렬을 해서
정렬된 만개의 정수를 200개의 파일에 쓴뒤 201번째 파일에 병합정렬을 하는 방법과,
(정렬된 데이터를 정렬할때는 병합정렬이 가장 빠르다고 알고있습니다)
처음부터 파일을 생성할때 정렬하지 않고 랜덤하게 생성해놓은다음
200만개의 정수를 한번에 퀵정렬로 정렬하여 파일에 쓰는 방법을 생각해 봤습니다.
제가 생각했을때는 처음 파일을 만들때부터 정렬하여 만든뒤 병합정렬로 정렬하여 201번째 파일에 쓰는 방법이 더 빠를거라 생각했는데,
오히려 200만개의 정수를 퀵정렬 한번하여 201번째 파일에 쓰는것이 더 빠르게 나오더군요.
그리고 정렬된 파일을 병합정렬로 201번째 파일에 쓰는것과
퀵정렬로 201번째 파일에 쓰는것을 비교해 보니, 병합정렬을 하는것보다 퀵정렬을 할때가 더 빠른경우도 자주 나타나던데 정렬된 데이터를 다시 정렬하여 넣을때
병합정렬이 가장 빠르다고 알고있던건 잘못 알고있던것인지, 아니면 그만큼 퀵정렬과 병합정렬의 차이가 크게 나지 않는것인지 궁금합니다.
요지는, 200만개의 랜덤한 정수를 만개단위로 끊어서 200개의 파일을 만든뒤 201번째 파일에 정렬해서 넣어야 한다면
어떻게 구현하는게 가장 빠를까요?
![[레벨:2]](http://old.lameproof.com/modules/point/icons/default/2.gif "포인트:588point (50%), 레벨:2/30"){kind=icon}
죠쨩
2009.05.25 09:54:34 (*.139.226.116)
마자마자 임의의 수는 0~32767 까지만 생성되기 때문에 많은 중복되는 수가 꽤 많습니다.
제가 할때는 어떻게 해봐도 200만개를 그냥 한번에 퀵정렬로 정렬하는게 가장 빠르더군요.
제가 할때는 어떻게 해봐도 200만개를 그냥 한번에 퀵정렬로 정렬하는게 가장 빠르더군요.
2009.05.25 11:24:32 (*.204.215.46)
![[레벨:4]](http://old.lameproof.com/modules/point/icons/default/4.gif "포인트:1482point (5%), 레벨:4/30"){kind=icon}
BubbleGum 하드가 비교적 느리기 때문에 어떻게 구현을 하던간에 하드를 읽고 쓰는 횟수를 가장 적게 하는 방법이 가장 빠릅니다.
ps. 생각하는 프로그래밍이란 책에 나온 알고리즘을 응용하여 메모리를 아끼면서 결과를 낼수 있는 방법이 생각 났습니다.(아 책을보니 그 알고리즘이 죠짱님이 말하신 비트맵 정렬인것 같습니다.)
임의의 수는 0~32767까지 생성되기 때문에 그 범위 안의 그 숫자들이 몇개씩 있는지 센다음에 0부터 그 갯수만큼씩 201번째 파일에 출력하면 됩니다.
1. int count[32768]; 이런 배열을 만들고서 모두 0으로 초기화 시켜 줍니다.
2. 200개의 파일을 읽어오면서 지금 읽은 숫자가 만약 999라면 count[999]++; 이런식으로 위의 배열을 숫자들의 카운터로 사용합니다.
3. 201번째 파일에 count[0]이 3이면 "0 0 0 " 출력하고 이어서 count[1]이 5면 "1 1 1 1 1 " 이런식으로 count[32767]까지 하면 됩니다.
하드에선 한번 읽고 한번 씁니다.
ps. 생각하는 프로그래밍이란 책에 나온 알고리즘을 응용하여 메모리를 아끼면서 결과를 낼수 있는 방법이 생각 났습니다.(아 책을보니 그 알고리즘이 죠짱님이 말하신 비트맵 정렬인것 같습니다.)
임의의 수는 0~32767까지 생성되기 때문에 그 범위 안의 그 숫자들이 몇개씩 있는지 센다음에 0부터 그 갯수만큼씩 201번째 파일에 출력하면 됩니다.
1. int count[32768]; 이런 배열을 만들고서 모두 0으로 초기화 시켜 줍니다.
2. 200개의 파일을 읽어오면서 지금 읽은 숫자가 만약 999라면 count[999]++; 이런식으로 위의 배열을 숫자들의 카운터로 사용합니다.
3. 201번째 파일에 count[0]이 3이면 "0 0 0 " 출력하고 이어서 count[1]이 5면 "1 1 1 1 1 " 이런식으로 count[32767]까지 하면 됩니다.
하드에선 한번 읽고 한번 씁니다.
2009.05.25 13:08:46 (*.139.226.116)
마자마자 생각해보니 하드에서 읽고 쓰는 횟수는 어떤식으로 짜던 똑같네요.
쓰는건 10000개씩 200번 + 201번째의 파일에 쓰는 200만번
읽는건 10000개씩 200번.
결국 정렬 알고리즘과 정렬하는 위치를 활용해서 해결해야 하는건데,
그냥 하기만 하는게 아니라 최대한 빠른 시간을 끌어내야 하니까 여러모로 생각할게 많네요...
쓰는건 10000개씩 200번 + 201번째의 파일에 쓰는 200만번
읽는건 10000개씩 200번.
결국 정렬 알고리즘과 정렬하는 위치를 활용해서 해결해야 하는건데,
그냥 하기만 하는게 아니라 최대한 빠른 시간을 끌어내야 하니까 여러모로 생각할게 많네요...
2013.05.19 12:58:26 (*.153.235.115)
![[레벨:3]](http://old.lameproof.com/modules/point/icons/default/3.gif "포인트:962point (24%), 레벨:3/30"){kind=icon}
bestbasci01@yahoo.com
중복이 안되면 비트맵정렬이고..
중복이 되면 그냥 뭐 해봐야 알죠.