-
알고리즘 - Bubble Sort (버블 소트)를 코딩해보자(2)Knowledge/Algorithm 2019. 6. 15. 15:38
https://shineild-security.tistory.com/17
https://shineild-security.tistory.com/18
안녕하세요 지난번 포스팅에 이어서 Bubble sort 마지막 게시글이 될 세번째 들을 포스팅하게 되었습니다.
지난번엔 데이터를 배열형태로 구성하였을때 저울을 어떻게 설계해야 할지 뇌정지가 와서 굉장히 복잡한 방법으로 구성을 해보았었는데요.
오늘은 어떻게 하면 좀 더 효율적인 코딩을 할 수 있을지 생각하며 전에 작성하지 못했던 배열형태로 작성해보았습니다.
저울을 어떻게 해야할지 고민을 좀 했었는데 영감을 얻게해주신 페페님께 진심으로 감사의 말씀을 전해드리고 싶네요.(__)
#include <stdio.h> typedef struct scale{ int * left; int * right; int cnt; }scale; int main(int argc, const char * argv[]) { int num; printf("데이터 개수 입력 : "); scanf("%d", &num); int bubble[num]; for (int i = 0; i < num; i++){ printf("데이터 입력: "); scanf("%d", (bubble + i)); } int small, big; scale scale; for (int n = 0; n < (num-2); n++){ scale.cnt = 0; for (int i = (num-1); i > n; i--){ scale.left = (bubble + (i-1)); scale.right = (bubble + i); if (*(scale.left) > *(scale.right)){ small = *(scale.right); big = *(scale.left); *(scale.right) = big; *(scale.left) = small; (scale.cnt)++; } } if (scale.cnt == 0){ break; } } for (int i=0; i <num; i++){ printf("%d\n", *(bubble + i)); } return 0; }
약 50줄로 간결해진 코드를 만들 수 있었습니다.
드디어 만족 할만한 결과가 나와서 이젠 다른 분들의 코드를 검색해서 참조해 보았습니다.
int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9}; void sort() { int i, j; for(i = 0; i < 10; i++) for(j = i+1; j < 10; j++) if(arr[i] > arr[j]) // 왼쪽에 있는 i번째 원소가 오른쪽에 있는 j번째 원소보다 크면은 두 원소를 바꾼다. { int t; t = arr[j]; arr[j] = arr[i]; arr[i] = t; } }
출저: https://librewiki.net/wiki/시리즈:수학인듯_과학아닌_공학같은_컴퓨터과학/알고리즘_기초
무려 15줄밖에 되지않는 짧은 코드입니다.
하지만 데이터 입력과 결과 출력은 제외한 코드여서 제가 작성한 코드와 길이상으론 큰 차이가 없어보입니다.
하지만 여기서 코드를 보고 저 또한 수정할 수 있는 부분들이 눈에 보였습니다.
1. 임시로 저장할 데이터를 담을 공간은 big, small 2개가 아닌 1개만 담아도 충분하다는 점.
2. 저울을 가시적으로 구성할 필요가 없다는 점.
3. 저는 알고리즘 도감이라는 어플을 참고로 작성하였는데 이 코드를 보면 원리가 살짝 다릅니다.
이중 for문을 돌림에 있어서 자세히 보면 바깥의 for문에 정의된 인덱스의 배열을 내부 for문을 통해서 전체적으로 하나씩 비교하며 데이터들을 밀어내는 방식이였습니다.
가령 예를 들면
4 2 7 1
이란 데이터가 있을 때
바깥 for문에선 인덱스0번인 데이터 4를 기준으로
내부 for문에서는 인덱스 1~3번인 2, 7, 1 을 비교하고 바깥 for문의 4와 내부 for문에 데이터 중 바깥 for문의 데이터가 크면 서로의 위치를 교체하는 과정을 하고 있었습니다.
이 방법은 방금 코드 검색해서 조사하다가 알게되었으며 결론적으로는 같은 기준으로 데이터를 정렬하기 때문에 같은 방법인 것 같습니다.
이렇게하면 가시적으로 저울을 사용하지 않아도 데이터정렬에 문제가 없음으로 저도 저울 구조체를 제거하고 다시 수정을 하게 되었습니다.
그래서 제 코드에서 보완할 세가지 점을 수정해 보았습니다.
for (int n = 0; n < num; n++){ for (int i = n+1; i < num; i++){ if (bubble[n] > bubble[i]){ tmp = bubble[n]; bubble[n] = bubble[i]; bubble[i] = tmp; } } }
매우 간결해진 것을 볼 수가 있습니다.
#include <stdio.h> int main(int argc, const char * argv[]) { int num; printf("데이터 개수 입력 : "); scanf("%d", &num); int bubble[num]; for (int i = 0; i < num; i++){ printf("데이터 입력: "); scanf("%d", (bubble + i)); } int tmp; for (int n = 0; n < num; n++){ for (int i = n+1; i < num; i++){ if (bubble[n] > bubble[i]){ tmp = bubble[n]; bubble[n] = bubble[i]; bubble[i] = tmp; } } } for (int i=0; i <num; i++){ printf("%d\n", bubble[i]); } return 0; }
전체코드로 봐도 만족스럽네요.
다만 다른 사람이 적은 코드를 보고 참고해서 만들면서 느낀거지만 이렇게 짜게되면 결국 n = num-1 일때까지 무조건 for문을 실행시켜야 한다는 단점이 있어서 미리 정렬이 될 수도 있는 배열을 횟수가 낭비될 수도 있겠다는 생각이 들었습니다.
그럼 이걸로 Bubble Sort 구현은 마무리되었네요.
사실 비효율적인 이 배열은 잘 쓰이지 않지만... 만들기에 만만해서 도전하였습니다.
'Knowledge > Algorithm' 카테고리의 다른 글
알고리즘 - 이진탐색 코드를 짜보자(2) (0) 2019.06.22 알고리즘 - 이진탐색 코드를 짜보자(1) (0) 2019.06.21 알고리즘 - 이진탐색 알고리즘 개념 (0) 2019.06.17 알고리즘 - Bubble Sort (버블 소트)를 코딩해보자! (1) (0) 2019.06.15 알고리즘 - Bubble Sort 개념 (버블 소트) (0) 2019.06.13