프로그래밍

C언어 버킷정렬 질문 답변좀 부탁합니다..

C언어로 int arr[10]={77,39,71,21,25,18,26,92,12,68} 이라는 배열을 버킷정렬을 할려합니다

구글링을 해보고 해도 적당한게 없어 제가 직접 만들어 봤는데

버킷정렬을 제대로 했는지 평가좀 해주셨으면합니다

 

bucketsort1.png

bucketsort2.png

bucketsort3.png

 

코드 설명

 

1. bucket을 2차원 동적배열을 해서 bucket[10][10] 으로 동적배열을 함

(앞의 10은 10의자리 10~90 뒤의 10은 1의자리 0~9)

 

2. bucket 을 0으로 초기화를 함

 

3. arr의 원소가 0부터 9까지 차례로 bucket 에 정렬

(예를들면 71,31 이 있으면 arr[1][0]=71 , arr[1][1]=31 이런식으로 입력함)

 

4. bucket 정렬된 값을 다시 arr로 정렬

(이렇게 할경우 arr[10]={71,21,12,92,25,26,77,18,68,39] 로 정렬이됨)

 

5. bucket을 다시 0으로 초기화 시킨뒤 arr을 10의 자리수가 작은수대로 정렬함

( 지금 arr[0]=71인데 이 71을 bucket[7][0]=71로 입력해서 10의자리수대로 정렬함)

 

6. 정렬된 bucket을 순서대로 arr의 복사함

 

7. 정렬완료

 

 

그리고 만약 버킷정렬을 다른식으로 좀 더 간단하고 쉽게 구현할수 있으면

어떻게 할 수 있는지 알려주셨으면 합니다

19개의 댓글

2019.11.13

버켓 정렬이 뭔가 했더니 radix sort 같은 건가 보네

이차원 배열 안쓰고 입력하고 동일한 크기의 어레이 두개로 구현할수 있지 않을까? 어차피 필요한 메모리 공간은 입력 배열 이상이 아닐거 같은데

0
@foon

radix sort 같은거 맞음

 

나도 그걸 고민해봤는데

1차원 배열로 할꺼면 동적할당 할 필요없이

퀵소트나 버블소트같이 다른 정렬함수 쓰면

되더라고

 

굳이 2차원 배열로 나눈 이유는

큰 범주 예를들면 1의 자리 숫자가

0~9인걸로 나누고

1의 자리 숫자가 0인 경우가

arr의 원소 개수가 10이니 최대10개 까지

되니 2차원 배열 한거였어

 

근데 다시 생각해보면

1차원 배열로도 정렬이 가능할거같은대

한번 해봐야 될거 같다

 

어쨋든 저 사진의 코드가 얼추 radixsort 가 맞나요??

0
@foon

해봤는데 이차원 배열도 안쓰고 동일한 크기의 어레이 1개로 구현했음

(동적배열로 2개의 배열을 생성한게 아니라 1개의 배열만 생성했음)

int arr[10] 하고 bucket[10] 만 생성해서 구현했는데 되더라고

 

그나저나 저렇게 하는게 radixsort가 맞는지 알려줄수있음??

0
2019.11.14
@다음팟플레이어

자리수를 토대로 낮은 자리-> 높은 자리 순으로 정렬하는 알고리즘이잖아? 그럼 맞지

0
2019.11.13

5번 라인.

int** bucket = (int**)malloc(sizeof(int*) * 10);

 

7번라인

bucket[i] = (int*)malloc(sizeof(int) * n);

 

11번 라인.

for(int j = 0 ; j < n ; j++) {

 

...

 

아 뭐야. 총체적인 난국인데.

0
@나혼자선다

굳이 문제될거 없다 보는데

n도 10이니까

 

10이라고 쓴 이유는

0~9를 표현한거고

 

n이라고 쓴 이유는

배열의 원소개수가 매번 달라지니

원소의 개수를 표현할려고 쓴거고

 

그리고 결과적으로 정렬은 잘 되는데

어떤부분에서 잘못된건지 알려줄수 있어??

0
2019.11.14
@다음팟플레이어

문제될 것 없다고 생각하는 코드가 나중에 엉켜서 존나 문제가 되는건 상식이고.

그러니까 n과 10을 분리해서 써야 하는거고.

 

코드 분석하다 기가막혀서 말았는데, 결과적으로 정렬이 잘 되는게 맞긴 하냐?

것보다 컴파일이 되긴 해?

 

심지어 저게 버킷정렬이 맞아?

0
@나혼자선다

1. n과 10을 분리해야 된다는게

무슨 뜻인지 모르겠음

10은 큰 범주 1의 자리수를 나타내는 0~9를

배열로 넣어야되니 10인거고

 

n이라고 한 이유는 만약 int arr[10]이 아니라

int arr[20] 이면 그때마다 코드수정해서

20으로 고칠수 없으니

int n = sizeof(arr)/sizeof(int)로 표현한거였어

 

2. 버킷정렬이 이게 맞는지 몰라서 물어볼려고

글쓴건데 어떤게 버킷정렬인지 알 수 있어?

 

3. 결과적으로 이게 버킷정렬이든 아니든

컴파일 잘되고 정렬 잘됨

0
2019.11.14
@다음팟플레이어

그래 그러니까 네말데로 n을 써야 할 곳은 n을 쓰고 10을 써야 할 곳은 10을 써야지.

넌 막 아무데나 n썼다가 10 썼다가 맘데로 잖아.

거기다가 포인터도 엉망으로 쓰고.

 

어제 코드 보다가 짜증나서 말았는데, 다시 보니 버킷정렬은 맞기는 한데.

사실, 1~100까지만 정렬할 수 있는 코드는 정렬이라고 할 수도 없지.

0
@나혼자선다

n과 10문제는 무슨뜻인지 이해됐음

그건 그렇다 치고

 

또 포인터도 엉망으로 썼다는데

어디가 잘못됐는지 알려줄수 있어??

 

그리고 사실 1~100까지 정렬할수 있는 코드라

하는데 사실 내가 그걸 물어보고 싶은거였어

어떻게 하면 10자리대 100자리대

섞여있어도 정렬할수 있는지

이게 궁금했는데 어덯게 하면

자리수의 상관없이 정렬을 할 수 있는지

알려줄수 있어??

0
2019.11.14
@다음팟플레이어

포인터는 위에 7번라인 수정한거 써놓음.

32비트에서는 문제 없는데, 64비트에서는 좀 문제가 될 수도 있음.

 

자리수 3자리로 올라가면,

심플하게 생각하면 네가 짠것처럼

그걸 1, 10, 100으로 3번 돌리면 됨.

10^n자리수로 한번 소팅하는 함수를 만들어놓고 3번 돌리면 되지.

 

또 다른 방법은, 가장 큰 수를 찾아서 루트 씌우고 그 값으로 처리하는 방법이 있는데,

예를들어, 가장 큰 수가 255 라고 하면,

루트씌우면 15.xxx 그걸 자연수로 만들고 1 더하면 16.

배열을 16개를 만들어서 %16 /16 으로 돌려도 되지.

이 방법의 문제점은, 데이터의 개수와 숫자의 크기가 커지면 자칫하면 메모리가 부족해질 수도 있다는거.

 

나라면 배열 16개씩 만들어서

8번 돌리면 uint 범위는 다 커버됨.

0
@나혼자선다

아.. 잘보니 포인터 오타였네

bucket[i] = (int*)malloc(sizeof(int)*n)이 맞지

위에 동적할당 하면서 그대로

sizeof(int*) 쓴듯

 

10^n자리수로 한번 소팅할까도 생각했는데

그러면 math.h 함수를 써야되는데

그게 싫어서

먼저 최대 10^n자리수 찾아논다음에

 

1의자리수는 따로 빼놓고 정렬하고

그다음에 10^n자리수로 천천히 소팅해도 되지??

 

예) arr의 원소중 최대값 10의자리 100의자리 1000의자리 등등 총 몇번째 자리까지 있는지 파악하고 그리고 나서 1의자리수만 따로 정렬하고

그다음에 for문이나 while문으로 최대자리수까지

소팅해도 똑같지?

0
2019.11.14
@다음팟플레이어

 

sortdigit(int* arr, int n, int d)

{

  int* bucket[10];

  int index[10];

 

  for( int i = 0 ; i < 10 ; i++) {

    bucket[i] = (int*)malloc(sizeof(int) * n);

    index[i] = 0;

  }

 

  for( int i = 0 ; i < n ; i++ ) {

    int insert = (arr[i] / d) % 10;

    bucket[insert][index[insert]++] = arr[i];

  }

 

  int k = 0;

  for( int i = 0 ; i < 10 ; i++) {

    for( int j = 0 ; j < index[i] ; j++) {

       arr[k++] = bucket[i][j];

    }

  }

 

  for( int i = 0 ; i < 10 ; i++) {

    free(bucket[i]);

  }

}

 

 

bucketsort(int *arr, int n)

{

  int max = 0;

  for( int i = 0 ; i < n ; i++)

  {

    if(max < arr[i])

      max = arr[i];

  }

 

  int d = 1;

  while(1)

  {

    sortdigit(arr, cnt, d);

    d *= 10;

    if(d > max)

      return;

  }

}

??

math.h가 어디들어가냐.

 

20분만에 대충 짜고 빌드도 안해봤더니 버그 겁나 많네 ㅋㅋㅋ

0
@나혼자선다

궁금한게 sortdigit(arr,cnt,d) 했는데

cnt가 어딨고 뭘 나타내는거야??

0
2019.11.14
@다음팟플레이어

버그 겁나 많네 ㅋㅋㅋ n이야.

0
2019.11.14
@다음팟플레이어

그리고 참고로, 10^n승 하려고 pow 들어있는 math.h쓰려고 한 것 같은데.

진짜 그런식으로 코딩하면 ㅈ돼.

진짜 진심 ㅈ돼.

 

이게 10을 float로 바꿀 때 9.999999가 됐다가 다시 int로 바꿀 때 9가 되는 경우가 있어.

문제는 너무 빈번하게 그런 일이 발생해서 존나 골치아파.

10^2 계산했는데 99 나오면 존나 데이터 다 꼬이는거야.

 

심지어는 엑셀에서도 그런 일이 발생함.

0
2019.11.14
@다음팟플레이어

근데 너 free도 안했다.

0
@나혼자선다

ㅇㅇ 프리도 오늘 수정했어

0
2019.11.14

나름 알고리즘 공부 좀 했다고 생각했는데 버킷정렬은 첨들어보네..

 

신기하네 이런정렬도 있고

 

쪼갰을때 순서가 있는 데이터에 대해서는 정렬이 다 될거 같네

0
무분별한 사용은 차단될 수 있습니다.
번호 제목 글쓴이 추천 수 날짜 조회 수
180032 [정보] 여기 사이트 믿을만 할까요 10 1542321542 0 3 시간 전 202
180031 [컴퓨터] Youtube Premium 광고 회피방법 8 도의지구 1 4 시간 전 343
180030 [정보] 윈도우 10 사용중인데 윈도우키+L 버튼 누르는 상태를 자동... 11 니말이맞아 0 4 시간 전 151
180029 [모바일] 애플워치 구형 중고 vs SE2 6 휴지를적당히사용... 0 5 시간 전 134
180028 [잡담] 구라도 적당히쳐야지 4 수육을쏘면탕수육 1 8 시간 전 242
180027 [컴퓨터] 유전원 usb 허브라고 문어발쓰다 죄다고장남 1 두뇌풀가동 0 11 시간 전 166
180026 [컴퓨터] 갤북4vs아이패드 신형 2 부두둥탁 0 11 시간 전 160
180025 [컴퓨터] 이거 모니터 고장난건가 2 EPS 0 13 시간 전 82
180024 [컴퓨터] 수냉쿨러 없었으면 덕트 쪽으로 컴터개발이 이루어 졋을듯 2 침혜랄 0 14 시간 전 177
180023 [컴퓨터] 요즘 보드들은 wifi가 신기하게 나오네 13 교미짝짓기 0 14 시간 전 305
180022 [잡담] 맥북 병은 사야 치료됨 11 장난없는사람 0 16 시간 전 301
180021 [컴퓨터] 모니터 이 둘 중이 뭐가 더 나음? 7 XDLOL 0 16 시간 전 155
180020 [컴퓨터] 모니터질문 or 추천좀용 10 20202021 0 18 시간 전 106
180019 [잡담] AI 요약 개웃기네 4 아도크 2 18 시간 전 323
180018 [컴퓨터] 모니터 사야하는데 11 XDLOL 0 19 시간 전 119
180017 [잡담] 크로미움 브라우저들 엔비디아 화면 깨지는 글리치 더 심해지네 1 ye 2 19 시간 전 134
180016 [잡담] s23 OneUI 6.1 업뎃 떴다 4 아도크 0 20 시간 전 350
180015 [컴퓨터] 영상편집용으로 프레데터 헬리오스 어떳슴까?? 2 으라야야 0 21 시간 전 89
180014 [잡담] 최근에 유튭프리미엄 우회 해본사람? 16 itx 0 21 시간 전 346
180013 [컴퓨터] 그래픽카드 하나 선물 해줘야 할거같은데 추천좀 13 침혜랄 0 22 시간 전 213