So i need all the help I can get on this question, i cant even start it other th

Question

So i need all the help I can get on this question, i cant even start it other than declaring a few variables and arrays :( please help... we are forbidden from using standard APIs that would otherwise implement data structures or sort functions or etc. Any data structure used must be programmed on our own

Sorting 3 a. Implement 3-way Quicksort for a linked list. Define these methods for the class i. LinkedList() constructor ii. add(int a); - Adds a number to the linked list ii printList) Prints the current list contents to console as comma separated values ("1,2,3" iv. quicksort) Runs 3-way quicksort. b. Your requirements for quicksort: i. It must shuffle the linked list. Note: there is no restriction on how you shuffle the list. It is up to you. We will test runtime for different insertions to validate the shuffle. i. It must print out every comparison and what is being compared. ii It should print out every swap. iv. It should print out the current list after finishing a partition (pivot is placed in final location). It should initially use median of 3 selection for the pivot in the first partition. For this problem, include only the class files/ code files. No main function file is needed. v. vi.

Explanation / Answer

// C++ program for 3-way quick sort

#include <bits/stdc++.h>

using namespace std;

  

/* This function partitions a[] in three parts

a) a[l..i] contains all elements smaller than pivot

b) a[i+1..j-1] contains all occurrences of pivot

c) a[j..r] contains all elements greater than pivot */

void partition(int a[], int l, int r, int &i, int &j)

{

i = l-1, j = r;

int p = l-1, q = r;

int v = a[r];

  

while (true)

{

// From left, find the first element greater than

// or equal to v. This loop will definitely terminate

// as v is last element

while (a[++i] < v);

  

// From right, find the first element smaller than or

// equal to v

while (v < a[--j])

if (j == l)

break;

  

// If i and j cross, then we are done

if (i >= j) break;

  

// Swap, so that smaller goes on left greater goes on right

swap(a[i], a[j]);

  

// Move all same left occurrence of pivot to beginning of

// array and keep count using p

if (a[i] == v)

{

p++;

swap(a[p], a[i]);

}

  

// Move all same right occurrence of pivot to end of array

// and keep count using q

if (a[j] == v)

{

q--;

swap(a[j], a[q]);

}

}

  

// Move pivot element to its correct index

swap(a[i], a[r]);

  

// Move all left same occurrences from beginning

// to adjacent to arr[i]

j = i-1;

for (int k = l; k < p; k++, j--)

swap(a[k], a[j]);

  

// Move all right same occurrences from end

// to adjacent to arr[i]

i = i+1;

for (int k = r-1; k > q; k--, i++)

swap(a[i], a[k]);

}

  

// 3-way partition based quick sort

void quicksort(int a[], int l, int r)

{

if (r <= l) return;

  

int i, j;

  

// Note that i and j are passed as reference

partition(a, l, r, i, j);

  

// Recur

quicksort(a, l, j);

quicksort(a, i, r);

}

  

// A utility function to print an array

void printarr(int a[], int n)

{

for (int i = 0; i < n; ++i)

printf("%d ", a[i]);

printf(" ");

}

  

// Driver program

int main()

{

int a[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};

int size = sizeof(a) / sizeof(int);

printarr(a, size);

quicksort(a, 0, size - 1);

printarr(a, size);

return 0;

}

Output:

4 9 4 4 1 9 4 4 9 4 4 1 4

1 1 4 4 4 4 4 4 4 4 9 9 9

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.