C : 배열에 대한 포인터 및 파괴적인 정렬

Question

간단한 코드를 썼습니다. bubbleSort는 버블 정렬 함수 (가장 작은 것부터 가장 큰 것)이고 int main은 크기가 5 인 int 배열로이 코드를 테스트하는 데 사용됩니다.

나는 이것을 파괴적으로 정렬하고 싶습니다. 배열을 복사하고 단순히 사본을 전달하는 것이 아닙니다. 나는 보았고 보았다. 그러나 나는 아직도 이것이 어떻게 작동해야하는지 완전히 명확하지 않다. 내가 여기서 무엇을 놓치고 있니?

#include <stdio.h> 

void bubbleSort(int values[], int n); 

int main(void) { 
//set simple test array to make sure bubbleSort works 
    int arr[5] = {5,4,3,2,1}; 
//run it through function, and then print the now sorted array to make sure 
    bubbleSort(arr, 5); 
    printf("%i", arr); 
    return 0; 
} 


void bubbleSort(int values[], int n) 
{ 
    for (int i = 0; i < n; i++) { 
     for (int j = 0, hold = 0; j < n-i; j++) { 
      if (values[j] > values[j+1]) { 
       hold = values[j+1]; 
       values[j+1] = values[j]; 
       values[j] = hold; 
      } 
     } 
    } 
    return; 
} 

참고 : 내 코드의 나머지 내 아마추어 코딩 마음에 소리 보이지만, 등, 무엇을 더 할 수있다, 내가 개선 할 수 있는지에 나에게 포인터를주고 내가 일종의하지만 거품에 대한 재귀를 사용하는 방법에 대한 생각하십시오 저는 아직 C를 사용하기에는 편하지 않습니다. 구현하고 싶습니다. 그러나 당신이 제안을 가지고 있다면 나는 그것들을 읽는 것보다 더 행복 할 것이다.

감사합니다.

Answer 1

함수가 배열을 정렬하는 것처럼 보이지만 (일부 버그가 있음에도 불구하고) 결과를 잘못 인쇄하고있는 것 같습니다. printf는 배열을 출력하는 방법을 모른다. 대신, 한 번에 각각의 정수를 인쇄하는 루프를 사용할 필요가 예상대로

for(int i=0; i<5; i++){ 
    printf("%d ", arr[i]); 
} 
printf("\n"); 

이를 변경 한 후, 출력은 1 2 3 4 5입니다.

그러나 의견에서 언급 한 바와 같이 bubblesort 구현에는 몇 가지 버그가 있습니다. 예를 들어 배열의 끝 부분에서 indedex의 요소를 읽으려고합니다. 이는 정의되지 않은 동작입니다 (즉, j+1은 범위를 벗어나 5이 될 수 있음). 나는 당신의 책을 다시 검사 하여서 bubblesort를 올바르게 구현할 것을 권합니다.

Answer 2

코드에 이미 버그가 있지만 코드가 이미 배열을 정렬합니다. 코멘트의 주제가 이미 sort 함수로 강조 표시된 것처럼 질문의 주제 (C로 배열의 적절한 정렬) 만 다루겠다.

는 정수로 arr 포인터를 인쇄하려고로 결과의 프린트 아웃하지만 올바르지 않습니다

for (int i = 0; i < 5; i++) 
     printf("%i", arr[i]); 

적용된 수정의 문제 :

sort.c:10:18: warning: format specifies type 'int' but the argument has type 'int *' [-Wformat] 
    printf("%i", arr); 
      ~~ ^~~ 
1 warning generated. 

그러나이 변경 산출.

아마도 배열은 실제로 C에서 포인터에 액세스하는 구문적인 방법에서 비롯된 것입니다. arr은 포인터입니다. arr[1]은 *(arr + 1)과 같습니다 (arr + 1 포인터 연산을 사용하여 포인터를 sizeof 유형으로 증가시킵니다). 따라서 함수에 arr을 전달하면 기존 배열에 대한 포인터를 전달한 다음 해당 내용을 수정하여 배열을 적절한 위치에 정렬합니다.

Answer 3

버블 정렬 코드에는 이어야하며을 고정해야하는 문제가 하나 있습니다. 이 변경할 수 없기이다

/* for (int j = 0, hold = 0; j < n-i; j++) { */ // ISSUE here 
for (int j = 0, hold = 0; j < n-i-1; j++) { // j < n-i-1 should be the condition 

, 외부 루프의 i = 0, 즉 제 iterartion 경우을보기 : 내부 루프는 문제가있다.이번에는 j이 배열의 마지막 색인 인 n보다 작 으면 j < n - i이 true가됩니다. 그런 다음 values[j]과 values[j+1] 사이에서 충돌합니다. 여기서 values[j+1]은 분명히 배열 범위를 벗어납니다. 그러면 undefined behavior이 호출되며 함수가 결정적인 결과를 제공하지 않습니다.

다음 개선 사항은 외부 루프가 i = 0 till i < n-1에서 반복해야한다는 것입니다. 즉 총 요소의 1 배 미만입니다. 필요한 것보다 한 번 더 중재하고 있습니다.

셋째로, 내부 루프에서 적어도 swap의 날씨를 추적하는 플래그를 사용할 수 있습니다. 내부 루프에 스왑이 없으면 배열이 이미 정렬되었음을 의미합니다. 그래서 내부 루프의 각 반복 끝에 스왑이 완료되었는지 확인할 수 있고 스왑이 수행되지 않은 경우 외부 루프에서 빠져 나옵니다. 배열이 이미 거의 정렬 된 경우 성능이 향상됩니다. 다른 사람들이 지적한 것처럼, 당신의 정렬 기능과 관련된 것은 아니지만

void bubbleSort(int values[], int n) 
{   
    int swap; // To use as a flag 

    // for (int i = 0; i < n; i++) { 
    for (int i = 0; i < n-1; i++) {     
      swap = 0;  // set swap flag to zero 
      // for (int j = 0, hold = 0; j < n-i; j++) { 
      for (int j = 0, hold = 0; j < n-i-1; j++) { 
        if (values[j] > values[j+1]) { 
          hold = values[j+1]; 
          values[j+1] = values[j]; 
          values[j] = hold; 
          swap = 1;  // swap was done 
        } 
      } 
      if (swap == 0) // If no swap was done 
        break; // Means array already sorted 
    } 
    return; 
} 

그리고, printf("%i", arr); 잘못이며, 당신이 printf에 잘못된 형식 지정자를 사용하고 있기 때문에 undefined behavior를 호출합니다. 배열을 인쇄하려고하는 것 같습니다. 이를 위해 당신이 할 수 있습니다 :

는

// printf("%i", arr); 
for (int i = 0; i < 5; i++) 
    printf("%d ", arr[i];) 
printf("\n");