What should I do for sort array?

Question

I tried to sort arr by excluding those who were already selected as the largest numbers but it didn't work.

The result is this:

As I intended, at first cycle, the store is {9, 0, 0, 0, 0 ... } and when arr[i] becomes 9, the rest of process should be skipped. I have to sort it without additional functions and it's too difficult to me. What is the problem?

int i = 0;
int j = 0;
int num = 0;
int sign = 0;
int arr[10] = { 1,5,3,4,8,7,5,9,8,0 };
int max = arr[0];
int store[10] = { 0 };
int k = 0;

for (j = 0; j < 10; j++) {
    printf("store: ");
    for (int n = 0; n < 10; on++)
        printf("%d ", store[n]);
    printf("\n");
    for (i = 0; i < 10; i++) {
        sign = 0;
        k = 0;
        while (k < 10) {
            if (arr[i] == store[k]) {
                sign = 1;
                break;
            }
            k++;
        }
        if (sign == 1) {
            continue;
        }

        if (arr[i] > max) {
            max = arr[i];
        }
    }

    store[j] = max;

}

http://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Biffen, Dec 11 '16 at 12:58
Possible duplicate of [C Array sorting tips](http://stackoverflow.com/questions/3893937/c-array-sorting-tips) — TigOldBitties, Dec 11 '16 at 13:01

score 1 · Answer 1 · answered Dec 11 '16 at 14:02

You have several errors here:

The array store has a size of 10, but in the jth pass through the outer loop, only j values have been filled in; the rest is still zero. So whenever you iterate over store, you should use j as upper limit.

You are looking for the max in each iteration. Therefore, it is not enough to initialise max once outside the outer loop. You do that, and it will stay 9 ever after. You should reset max for every j.

Finally, your idea to go through the array to see whether you have already processed a certain value does not work. Your array has duplicates, two 8's and two 5's. You will only place one eight and one five with your strategy and re-use the last value of max for the last two elements. (Plus, that idea lead to O(n³) code, which is very wasteful.

You can work around that by keeping an extra array where you store whether (1) or not (0) you have already processed a value at a certain index or by setting processed entries in the array to a very low value.

What you want to implement is selection sort: Find the maximum value in the whole list and move it to the front. Then find the maximum in the whole list except the first item and move it to the second slot and so on:

* 1 5 3 4 8 7 5 9 8 0 
9 * 5 3 4 8 7 5 1 8 0 
9 8 * 3 4 5 7 5 1 8 0 
9 8 8 * 4 5 7 5 1 3 0 
9 8 8 7 * 5 4 5 1 3 0 
9 8 8 7 5 * 4 5 1 3 0 
9 8 8 7 5 5 * 4 1 3 0 
9 8 8 7 5 5 4 * 1 3 0 
9 8 8 7 5 5 4 3 * 1 0 
9 8 8 7 5 5 4 3 1 * 0 
9 8 8 7 5 5 4 3 1 0 *

Here, all items to the left of the asterisk have been sorted and everything to the right of the asterisk is still unsorted. When the * (at position j) has moved to the right, the whole array is sorted.

This sort is in-place: It destroys the original order of the array. That is useful, because the position of an element tells us whether it has been processed or not. In the third iteration, the algorithm can distinguish between the 8 that has been sorted and the 8 that hasn't been sorted yet. (This sort is often described as sorting a hand of cards: Look fo the lowest, put it to the left and so on. If you must sort into a second array, copy the original array and sort the copy in place.)

Here's the code that sorts your array and prints out the diagram above:

#include <stdlib.h>
#include <stdio.h>

int main()
{
    int arr[10] = {1, 5, 3, 4, 8, 7, 5, 9, 8, 0};
    int i = 0;
    int j = 0;

    for (j = 0; j < 10; j++) {
        int imax = j;
        int swap = arr[j];

        // print array
        for (i = 0; i < 10; i++) {
            if (i == j) printf("* ");
            printf("%d ", arr[i]);
        }
        printf("\n");

        // find index of maximum item
        for (i = j + 1; i < 10; i++) {
            if (arr[i] > arr[imax]) {
                imax = i;
            }
        }

        // swap first unsorted item and maximum item
        arr[j] = arr[imax];
        arr[imax] = swap;
    }

    // print fully sorted array
    for (i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }
    printf("*\n");

    return 0;
}

score 0 · Answer 2 · answered Dec 11 '16 at 13:15

Use i and j.

N is 10 and the data consists of shuffled numbers 0 to N-1.

j goes from 0 to N-1. At each step, you want to fill it with the maximum of the unprocessed input.

So i goes from j+1 to N-1, in the inner loop. If arr[j] < arr[i], swap arr[i] and arr[j].

It speeds up considerably as you get towards the end.

What should I do for sort array?

2 Answers2