Day 20 Homework: Dynamic Data Structures

1. Write a program to implement the quick sort function on the list of numbers using an array

#include <stdio.h>
int partition(int a[], int p, int r);
void quicksort(int a[], int p, int r);

/* MAIN FUNCTION WITH PRE-DEFINED ARRAY OF ELEMENTS*/

int main(void){

int arr[] = {1,8,2,9,3,7,5,6,4};

quicksort(arr, 0, 8);



return 0;
}

/* RECURSIVE 'quicksort' FUNCTION CALL TO AN ARRAY, IS SEPARATED BY A PARTITION THAT IS INITIALIZED AS THE FIRST ELEMENT IN THE ARRAY AND SUBSEQUENT SUB-ARRAYS */

void quicksort(int a[], int p, int r)
{
  if (p < r)
  {
    int q;
    q = partition(a, p, r);
    quicksort(a, p, q);
    quicksort(a, q+1, r);
  }
}

/* 'partition' SWAPS THE PIVOT UNTIL ALL THE ELEMENTS GREATER ARE POSITIONED ABOVE IT, AND ALL THE ELEMENTS LESS THAN ARE POSITIONED BELOW */

int partition(int a[], int p, int r)
{

  int i, j, pivot, temp;
  pivot = a[p];
  i = p;
  j = r;

  while(1)
  {
    for(int i = 0; i < 9; i ++)
    {
      printf("%d ",a[i]);
    }
    printf("\n");
    while(a[i] < pivot)
      i++;

    while(a[j] > pivot)
      j--;

    if (i < j)
    {
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
    else
    {
      printf("%d ",j);
      printf("\n");
      return j;
    }

  }
}


2. Modify the program to work with a linked list.