Implement Pancake Sort on Array of Integers
#include
#include
#include
void do_flip(int *, int, int);
int pancake_sort(int *list, unsigned int length)
{
if (length < 2)
return 0;
int i, a, max_num_pos, moves;
moves = 0;
for (i = length;i > 1;i--)
{
max_num_pos = 0;
for (a = 0;a < i;a++)
{
if (list[a] > list[max_num_pos])
max_num_pos = a;
}
if (max_num_pos == i - 1)
continue;
if (max_num_pos)
{
moves++;
do_flip(list, length, max_num_pos + 1);
}
do_flip(list, length, i);
}
return moves;
}
void do_flip(int *list, int length, int num)
{
int swap;
int i = 0;
for (i;i < --num;i++)
{
swap = list[i];
list[i] = list[num];
list[num] = swap;
}
}
void print_array(int list[], int length)
{
int i;
for (i = 0;i < length;i++)
{
printf("%d ", list[i]);
}
}
int main(int argc, char **argv)
{
int list[9];
int i;
printf("enter the 9 elements of array:\n");
for (i = 0;i < 9;i++)
scanf("%d", &list[i]);
printf("\nOriginal: ");
print_array(list, 9);
int moves = pancake_sort(list, 9);
printf("\nSorted: ");
print_array(list, 9);
printf(" - with a total of %d moves\n", moves);
getch();
}
Output
enter the 9 elements of array:
10
9
8
7
6
5
4
3
2
Original: 10 9 8 7 6 5 4 3 2
Sorted: 2 3 4 5 6 7 8 9 10 - with a total of 0 moves
enter the 9 elements of array:
1
2
3
4
5
6
7
8
9
Original: 1 2 3 4 5 6 7 8 9
Sorted: 1 2 3 4 5 6 7 8 9 - with a total of 0 moves
enter the 9 elements of array:
5
6
7
8
9
1
4
2
3
Original: 5 6 7 8 9 1 4 2 3
Sorted: 1 2 3 4 5 6 7 8 9 - with a total of 3 moves
Implement Bogo Sort in an Integer Array
#include
#include
#include
#define size 7
int is_sorted(int *, int);
void shuffle(int *, int);
void bogosort(int *, int);
int main()
{
int numbers[size];
int i;
clrscr();
printf("Enter the elements of array:");
for (i = 0; i < size;i++)
{
scanf("%d", &numbers[i]);
}
bogosort(numbers, size);
printf("The array after sorting is:");
for (i = 0;i < size;i++)
{
printf("%d\n", numbers[i]);
}
printf("\n");
}
int is_sorted(int *a, int n)
{
while (--n >= 1)
{
if (a[n] < a[n - 1])
{
return 0;
}
}
return 1;
}
void shuffle(int *a, int n)
{
int i, t, temp;
for (i = 0;i < n;i++)
{
t = a[i];
temp = rand() % n;
a[i] = a[temp];
a[temp] = t;
}
}
void bogosort(int *a, int n)
{
while (!is_sorted(a, n))
{
shuffle(a, n);
}
}
Output
Enter the elements of array:56
34
96
26
08
87
36
The array after sorting is:8
26
34
36
56
87
96
Enter the elements of array:12
23
34
45
56
67
78
The array after sorting is:12
23
34
45
56
67
78
Worst case:
Enter the elements of array:984
38
983
389
37
596
483
The array after sorting is:37
38
389
483
596
983
984
No comments:
Post a Comment