Code:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void printdata(int x, int data[]);
int basicsort(int x, int data[]);
int middlesort(int x, int data[]);
int firstoptimumsort(int x, int data[]);
int secondoptimumsort(int x, int data[]);
int main()
{
int data[] = {5, 8, 12, -6, 98, 56, -19, 4, 17, 18, 3, -2, 7, 10, -5, 22, 1, 27, 25, 30};
int num_data_items = 20, count;
printf("Original order of data items:\n");
printdata(num_data_items, data);
count = firstoptimumsort(num_data_items, data);
printf("\nData items in ascending order:\n");
printdata(num_data_items, data);
printf("\ncount is %d\n", count);
return 0;
}
void printdata(int x, int data[])
{
int i;
for (i = 0; i < x; i++)
{
printf("%d ", data[ i ]);
}
}
int basicsort(int x, int data[])
{
int pass, i, temp, count_inner = 0, count_outter = 0;
for (pass = 0; pass < x - 1; pass++)
{
for (i = 0; i < x - 1; i++)
{
if (data[ i ] > data[ i + 1])
{
temp = data[ i ];
data[ i ] = data[ i + 1 ];
data[ i + 1 ] = temp;
}
count_inner++;
}
count_outter++;
printf("\nafter %d pass(s) ", count_outter);
printdata(x, data);
}
return count_inner;
}
int middlesort(int x, int data[])
{
// added in a sorted flag to limit it trys to sort a sorted array
int pass, i, temp, count_inner = 0, count_outter = 0;
bool data_swapped;
for (pass = 0; pass < x - 1; pass++)
{
data_swapped = false;
for (i = 0; i < x - 1; i++)
{
if (data[ i ] > data[ i + 1])
{
temp = data[ i ];
data[ i ] = data[ i + 1 ];
data[ i + 1 ] = temp;
data_swapped = true;
}
count_inner++;
}
count_outter++;
printf("\nafter %d pass(s) ", count_outter);
printdata(x, data);
if (!data_swapped)
{
break;
}
}
return count_inner;
}
int firstoptimumsort(int x, int data[])
{
//subtract the value of pass from the second loop
int pass, i, temp, count_inner = 0, count_outter = 0;
bool data_swapped;
for (pass = 0; pass < x - 1; pass++)
{
data_swapped = false;
for (i = 0; i < x - pass - 1; i++)
{
if (data[ i ] > data[ i + 1])
{
temp = data[ i ];
data[ i ] = data[ i + 1 ];
data[ i + 1 ] = temp;
data_swapped = true;
}
count_inner++;
}
count_outter++;
printf("\nafter %d pass(s) ", count_outter);
printdata(x, data);
if (!data_swapped)
{
break;
}
}
return count_inner;
}
int secondoptimumsort(int x, int data[])
{
//substitute the index of the last number swapped for x - pass - 1 in the second loop
int pass, i, temp, count_inner = 0, count_outter = 0, index_num_swapped = x - 1, tmp_index;
bool data_swapped;
for (pass = 0; pass < x - 1; pass++)
{
data_swapped = false;
for (i = 0; i < index_num_swapped; i++)
{
if (data[ i ] > data[ i + 1])
{
temp = data[ i ];
data[ i ] = data[ i + 1 ];
data[ i + 1 ] = temp;
data_swapped = true;
tmp_index = i;
}
count_inner++;
}
index_num_swapped = tmp_index;
count_outter++;
printf("\nafter %d pass(s) ", count_outter);
printdata(x, data);
if (!data_swapped)
{
break;
}
}
return count_inner;
}
the basic one took 361 goes middle took 247 firstoptimum took 169 and second one took 141.