task 8

#include<stdio.h>
#include<stdlib.h>
//#include"list.h"

// List element: a list is a chain of these
typedef struct element
{
  int val;
  struct element* next;
} element_t;
// List header - keep track of the first and last list elements
typedef struct list
{
  element_t* head;
  element_t* tail;
} list_t;

list_t* list_create( void )
{
  list_t* l =  malloc( sizeof(list_t) );
  if(l){
l->head = NULL;
l->tail = NULL;
  }
}

void list_destroy( list_t* list )
{
  element_t* el = list->head;
  while( el )
    {
      element_t* next = el->next;
      free( el );
      el = next;
    }

  free( list );
}
element_t* element_create( int i )
{
  element_t* el = malloc( sizeof(element_t) );
  if( el )
    {
      el->val = i;
      el->next = NULL;
    }
  return el;
}

int list_append( list_t* list, int i )
{
  element_t* el = element_create( i );
  if( el == NULL )
    return 1;

  if( list->head == NULL )
    list->head = el;

  if( list->tail )
    list->tail->next = el;

  list->tail = el;
  return 0;
}

void list_print( list_t* list )
{
  printf( "{" );

  for( element_t* el = list->head;
       el;
       el = el->next )
    printf( " %d", el->val );

  printf( " }\n" );
}

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

void swap(int a[], int i, int j) //swaps values using their indices
{
  int x = a[i];
  a[i] = a[j];
  a[j] = x;
}

/*int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(arr, i, j);
        }
    }
    swap(arr, (i + 1), high);
    return (i + 1);
}*/

int partition(int list[], int low, int high)
{
  int pivot = list[low];
  int pi = low; //pivot starting index
  int i = low; int j = high;
  while(i!=j){
    if(pi == i){
      if(list[j] < pivot){
        swap(list,i,j);
        pi = j;
        i++;
      } else { //when the j->val is greater than pivot
        j--;
      }
    }else{//when the pivot index is at the j value instead
      if(list[i] > pivot){
        swap(list, i, j);
        pi = i;
        j--;
      } else {
        i++;
      }
    }
  }
  return pi;
}

void quicksort(int list[], int low, int high)
{
  if(low < high){
    int pivot = partition(list, low, high);
    quicksort(list, low, pivot-1);
    quicksort(list, pivot+1, high);
  }
}

void list_sort(list_t* list)
{
  int n = arrLength(list)-1;
  int* p = malloc(sizeof(int)*(n+1));
  //appends the elements the elements of the linked list to new array
  element_t* el = list->head;
  for(int i =0; i<=n; i++){
    p[i] = el->val;
    el = el->next;
  }
  //sorts the list
  quicksort(p, 0, n);
  //puts the elements back into linked list

  int k =0;
  //while(el)
  for(element_t* el1 = list->head; el1; (el1 = el1->next) && k++)
    el1->val = p[k];
    //k++;
}

int main()
{
  list_t* list = list_create();

  list_append(list, 3);
  list_append(list, 2);
  list_append(list, 8);
  list_append(list, 5);
  list_append(list, 7);

  list_sort(list);
  list_print(list);
  list_destroy(list);

  return 0;
}