Scribd
Upload
4 views4 pages

Quick Sort Report

Quick Sort is an efficient divide-and-conquer sorting algorithm that selects a pivot, partitions the list into sublists, and recursively sorts them. The algorithm is effective for large lists with an average time complexity of O(n log n), but it is not stable. Quick Sort is particularly advantageous for linked lists due to its pointer-based partitioning method.

Uploaded by

shybbwqadt
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views4 pages

Quick Sort Report

Quick Sort is an efficient divide-and-conquer sorting algorithm that selects a pivot, partitions the list into sublists, and recursively sorts them. The algorithm is effective for large lists with an average time complexity of O(n log n), but it is not stable. Quick Sort is particularly advantageous for linked lists due to its pointer-based partitioning method.

Uploaded by

shybbwqadt
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

# Quick Sort

## Definition

Quick Sort is an efficient divide■and■conquer sorting algorithm.

It selects a *pivot* element, partitions the list into two sublists (elements less than the pivot and
elements greater than the pivot), then recursively sorts the sublists.

---

## Algorithm

1. Choose a pivot.

2. Partition the list into:

- Left: elements < pivot

- Right: elements ≥ pivot

3. Recursively apply Quick Sort to left and right lists.

4. Combine the results.

---

## Example

Given the list:

`[7, 3, 9, 2]`

- Pivot = 7

- Left = [3, 2]

- Right = [9]

- Sort left → [2, 3]

- Final result → `[2, 3, 7, 9]`

---

## Quick Sort on Linked List (C Code)


```c

typedef struct Node {

int data;

struct Node* next;

} Node;

Node* partition(Node* head, Node** newHead, Node** newEnd) {

Node* pivot = head;

Node* prev = NULL, *cur = head->next, *tail = pivot;

while (cur != NULL) {

if (cur->data < pivot->data) {

if (!*newHead) *newHead = cur;

prev = cur;

cur = cur->next;

} else {

if (prev) prev->next = cur->next;

Node* tmp = cur->next;

cur->next = NULL;

tail->next = cur;

tail = cur;

cur = tmp;

if (!*newHead) *newHead = pivot;

*newEnd = tail;

return pivot;

}
Node* quickSortRec(Node* head, Node* end) {

if (!head || head == end) return head;

Node *newHead = NULL, *newEnd = NULL;

Node* pivot = partition(head, &newHead;, &newEnd;);

if (newHead != pivot) {

Node* tmp = newHead;

while (tmp->next != pivot) tmp = tmp->next;

tmp->next = NULL;

newHead = quickSortRec(newHead, tmp);

Node* tail = newHead;

while (tail->next) tail = tail->next;

tail->next = pivot;

pivot->next = quickSortRec(pivot->next, newEnd);

return newHead;

Node* quickSort(Node* head) {

Node* end = head;

while (end && end->next) end = end->next;

return quickSortRec(head, end);

```

---

## Comparison (Linked List)


- **Efficient for large lists**

- **Fast average time**: O(n log n)

- **Not stable**

- **Good for linked lists** because partitioning is pointer■based and does not require shifting
elements.

You might also like