Sinisterly
C++ sorting arrays - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: C, C++, & Obj-C (https://sinister.ly/Forum-C-C-Obj-C)
+--- Thread: C++ sorting arrays (/Thread-C-sorting-arrays)

C++ sorting arrays - ICE_ - 06-18-2013

before I begin i'd like to say this is 100% MINE i am just transferring from SF

Source Code:

Code:
#include <iostream>

using namespace std;

int findSmallestRemainingElement(int array[], int size, int index);
void swap(int array[], int first_index, int second_index);

void sort(int array[], int size){
    for(int i = 0; i < size; i++){
        int index = findSmallestRemainingElement(array, size, i);
        swap(array, i, index);
    }
}
int findSmallestRemainingElement(int array[], int size, int index){
    int index_of_smallest_value = index;
    for(int i = index + 1; i < size; i++){
        if(array[ i ] < array [ index_of_smallest_value ] ){

                index_of_smallest_value = i;
        }
    }
    return index_of_smallest_value;
}

void swap(int array[], int first_index, int second_index){
    int temp = array[first_index];
    array[first_index] = array[second_index];
    array [second_index] = temp;
}
void displayArray(int array[], int size){
    cout <<"{";
    for ( int i = 0; i < size; i++){
    if ( i != 0){
        cout <<", ";
    }
    cout << array[i];
    }
    cout << "}";
}
int main(){
    int array[10];
    srand(time(NULL));
    for(int i = 0; i <10; i++){
    array[i] = rand() % 100;
    }
    cout << "Original array: ";
    displayArray(array,10);
    cout<<'\n';

    sort(array,10);
    cout<<"Sorted array: ";
    displayArray(array,10);
    cout<<'\n';
}

Array sorting is taking an array of random, unsorted (from least to greatest) numbers and sorting them out (from least to greatest).

To do this we must use a sorting algorithm:

Take the index (the place in the array) where the first number is.
Look at this number.
Take the index (the place in the array) where the second number is.
Look at this number.
If the first number is larger then the second number swap them.
If the second number is larger then the first number swap them.
Move on to the next 2 indexes.
Repeat until array is sorted.




Lets take a look at the source code piece by piece starting with the first function:
________________________
The sort function:


Code:
void sort(int array[], int size){
    for(int i = 0; i < size; i++){
        int index = findSmallestRemainingElement(array, size, i);
        swap(array, i, index);
    }
}

This method is the main algorithm for the entire program.

Lets take it piece by piece:

Code:
void sort(int array[], int size){

"int array[]" is the main array that we will be using, it is the array we will be putting random numbers in and sorting.
"int size" is the size of the array.

Code:
for(int i = 0; i < size; i++){
        int index = findSmallestRemainingElement(array, size, i);

while int i is less then the size of the array, set 'index' to the smallest remaining element in the array.

array = the array we are using
size = size of the array
i = index number that we are currently at


Code:
swap(array, i, index);

go to the swap method and sort out these current indexes in the array
________________________
findSmallestRemainingElement function


Code:
int findSmallestRemainingElement(int array[], int size, int index){
    int index_of_smallest_value = index;
    for(int i = index + 1; i < size; i++){
        if(array[ i ] < array [ index_of_smallest_value ] ){

                index_of_smallest_value = i;
        }
    }
    return index_of_smallest_value;
}

This function gets the current,previous and next index of the array and compares them (to see if which is biggest/smallest).

Code:
int findSmallestRemainingElement(int array[], int size, int index){

array[] - the array we are using
size - the size of the array
index - the index we are at
Code:
int index_of_smallest_value = index;

takes the index number from the function ( "int findSmallestRemainingElement(int array[], int size, int index){" ) and sets it to "index_of_smallest_value"

Code:
for(int i = index + 1; i < size; i++){
        if(array[ i ] < array [ index_of_smallest_value ] ){
while 'i',which is the index number in front of the index number used in 'index_of_smallest_value" is less then the index_of_smallest_value...


Code:
index_of_smallest_value = i;

set the index_of_smallest_value to 'i', and repeat the loop


Code:
return index_of_smallest_value;
get the new index_of_smallest_value

________________________
Swap function

Code:
void swap(int array[], int first_index, int second_index){
    int temp = array[first_index];
    array[first_index] = array[second_index];
    array [second_index] = temp;
}

This function swaps the smallest number with the biggest number so that they are in least-to-greatest order.

Code:
void swap(int array[], int first_index, int second_index){

array[] - the array we are using
first_index - the index of the first number
second_index - the index of the second number

Code:
int temp = array[first_index];
    array[first_index] = array[second_index];
    array [second_index] = temp;

create a new integer names temp and set it as the first_index. Then set the first index to the second index (this should make array[second_index] and array[first_index] the same thing). Finally, set the second index to the original first index, visually this is:

first_index = 7 (original)
second_index= 6 (original)

temp = first index (temp = 7)
first index = second index ( first index = 6)

second index = temp (second index = 7)

first_index = 6 (new)
second_index = 7 (new)
________________________
displayArray function


Code:
void displayArray(int array[], int size){
    cout <<"{";
    for ( int i = 0; i < size; i++){
    if ( i != 0){
        cout <<", ";
    }
    cout << array[i];
    }
    cout << "}";
}

This function prints out the array.

Code:
void displayArray(int array[], int size){

array[] - array we are using
size - size of the array


Code:
cout <<"{";
    for ( int i = 0; i < size; i++){
    if ( i != 0){
        cout <<", ";
starts the print out of the array with '{' then goes through the array and checks if the index does not = 0, if so, a comma is appended into the array so that it looks like "1,2,3,4,5"

Code:
cout << array[i];
prints out the number in the current index of the array.


Code:
cout << "}";

ends the array-print out with a '}'

(the array should look like "{1,2,3,4,5,6}")

________________________
The main function

Code:
int main(){
    int array[10];
    srand(time(NULL));
    for(int i = 0; i <10; i++){
    array[i] = rand() % 100;
    }
    cout << "Original array: ";
    displayArray(array,10);
    cout<<'\n';

    sort(array,10);
    cout<<"Sorted array: ";
    displayArray(array,10);
    cout<<'\n';
}

This is the main function in every program. (like public static void main in java)

Code:
int array[10];
    srand(time(NULL));
    for(int i = 0; i <10; i++){
    array[i] = rand() % 100;
    }

sets the array size to 10, creates a random number object, creates a for loop that will set each index of the array to a random number

Code:
cout << "Original array: ";
    displayArray(array,10);
    cout<<'\n';

    sort(array,10);
    cout<<"Sorted array: ";
    displayArray(array,10);
    cout<<'\n';

prints out the array sorted and unsorted.


________________________
The outcome

The outcome of this program should be:

Original array: {94, 51, 85, 88, 15, 15, 56, 59, 63, 66}
Sorted array: {15, 15, 51, 56, 59, 63, 66, 85, 88, 94}


NOTE: the numbers in the above arrays were random and may not be the same for you.