I was doing selection sort yesterday. I wondered if I could replace the min and max values to begining and end of the unsorted array every time I iterated. I am just a beginner at programming, so its obvious that this wouldn't work. However, suprisingly, the code below does sort a larger array (~ 30k - 40k) in size. I experimented by generating random values from rand() 00 and the function sorted the array successfully 28 times in 30 experiments.

But it can't sort something as simple as {4,2,3} I think there's a bug somewhere, I couldn't figure it out so I've come here.

I'm also curious about the fact that it sorted such large arrays successfully. How?

int *zigzag_sort(int arr[])
{
    // loop through array
    // find min and max
    // replace min at begining and max at end
    // keep doing until sorted

    int f_idx = 0, l_idx = n-1;
    int min_pos, max_pos;
    
    while( f_idx < l_idx ) {
        min_pos = f_idx;
        max_pos = l_idx;
        
        for(int i = f_idx 1; i <= l_idx; i  ) 
        {
            if(arr[i] < arr[min_pos])
                min_pos = i;
            else if(arr[i] > arr[max_pos])
                max_pos = i;
        }           
        swap(&arr[f_idx], &arr[min_pos]);
        swap(&arr[l_idx], &arr[max_pos]);

        f_idx  ; 
        l_idx--;
        }
        
    return arr;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

CodePudding user response：

Why doesn't it work for { 4, 2, 3 }?

    ... // f_idx = 0; l_idx = 2; min_pos = 1; max_pos = 0;
    swap(&arr[f_idx], &arr[min_pos]); // swap(&arr[0], &arr[1]) ==> { 2, 4, 3 }
    // ===> max_pos is "wrong" now <===
    swap(&arr[l_idx], &arr[max_pos]); // swap(&arr[2], &arr[0]) ==> { 3, 4, 2 }

CodePudding user response：

Your swaps are not as simple as you think, and there is a hole in your position starting points going in to the inner loop iterations.

First, there are there situations that must be accounted after completing a segment enumeration and finding the segment min-index and max-index locations. They all deal with where you're reading data from, and where you'r'e trying to write it to. There can be partial, or in one case, full, overlap.

After each inner iteration, one of several conditions can transpire...

1. (min_pos == l_idx) && (max_pos == f_idx) . In other words, the minimum and maximum values are each in the places where the other wants to be. If that is the case ONE swap is needed (each other) and you're done for that iteration.

2. One of (min_pos == l_idx) or (max_pos == f_idx) is true, but not both. The order of the impending two swaps is important, depending on which of those conditions is true. In short, don't swap something into a slot that is about to be swapped again with the second swap. Ex: If the maximum value resides at the low target position, you need to swap it out to the maximum target position before the minimum value is swapped to the low target position. Otherwise you will dislocate something right after you put it home.

3. Neither of the above are true, in which case two swaps are still required, but order is irrelevant.

The probability of the special cases in (1) and (2) above increase significantly as you squeeze the iteration window down further and further during the outer loop iteration. For a random ordering, sooner or later it is going to happen.

Secondly, both the min_pos and max_pos starting points should be the same location in the segment, f_idx. It may not seem important, but it is so because the inner loop starts a f_idx 1. that means if the maximum value of the iteration was originally at f_idx you never accounted for it, will not discover it, etc.

The fixed routine is below, with notes where appropriate.

int *zigzag_sort(int arr[], int n)
{
    int f_idx = 0, l_idx = n - 1;

    while (f_idx < l_idx)
    {
        // both should start at the same location
        int min_pos = f_idx;
        int max_pos = f_idx;

        for (int i = f_idx   1; i <= l_idx; i  )
        {
            if (arr[i] < arr[min_pos])
                min_pos = i;
            else if (arr[i] > arr[max_pos])
                max_pos = i;
        }

        if (max_pos == f_idx)
        {
            if (min_pos == l_idx)
            {
                // swap each other
                swap(&arr[max_pos], &arr[min_pos]);
            }
            else
            {   // swap the max out before overwritine with min
                swap(&arr[l_idx], &arr[max_pos]);
                swap(&arr[f_idx], &arr[min_pos]);
            }
        }
        else
        {   // also handle the case of l_idx == min_pos
            swap(&arr[f_idx], &arr[min_pos]);
            swap(&arr[l_idx], &arr[max_pos]);
        }

        f_idx  ;
        l_idx--;
    }

    return arr;
}