[go: up one dir, main page]
Scribd
Upload
79 views10 pages

Examples: Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort

Internal sorting involves sorting data within main memory using algorithms like bubble sort, insertion sort, merge sort, quick sort, and heap sort. External sorting is used when data exceeds main memory size, using algorithms that write to external storage like disks. The document then provides pseudocode for bubble sort, insertion sort, merge sort, quick sort, and heap sort algorithms.

Uploaded by

uttam
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
79 views10 pages

Examples: Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort

Internal sorting involves sorting data within main memory using algorithms like bubble sort, insertion sort, merge sort, quick sort, and heap sort. External sorting is used when data exceeds main memory size, using algorithms that write to external storage like disks. The document then provides pseudocode for bubble sort, insertion sort, merge sort, quick sort, and heap sort algorithms.

Uploaded by

uttam
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
You are on page 1/ 10

Sorting: Arranging the records in a specific manner, say ascending oreder,

descending order etc.


Name Ad. No. Br dsM hghg
Ayush 19Jenjg cse 98, 76,
DD 19 EE 87, 67

Internal Sorting: If the whole table is sorted in the main memory


Examples: Bubble sort, insertion sort, merge sort, quick sort, heap sort
External Sorting: if it takes the help of external memory
Examples: address calculation sort.
Bubble Sort

Procedure Bubble_Sort (K, N)


1. LAST ← N

2. Repeat thru step 5 for PASS = 1, 2, ..., N – 1

3. EXCHS ← 0

4. Repeat for I = 1, 2, ..., LAST – 1


If K[I] > K[I + 1] then
K[I] ↔ K[I + 1]
EXCHS ← EXCHS + 1

5. If EXCHS = 0 then
Return
else LAST ← LAST – 1

6. Return

Time Complexity:
No. of Comparisons:
No. of Exchanges:
Insertion Sort

Time Complexity:
Merge Sort

Consider the following two sorted tables:


Table 1: 11, 23, 42
Table 2: 9, 25

Let us merge them as follows:

The two tables in the current example could be stored in a common array K as
follows:
Procedure MERGE_SORT(K, FIRST, SECOND, THIRD)

1. I ← FIRST
J← SECOND
L← 0

2. Repeat While I < SECOND and J ≤ THIRD


If K[I] ≤ K[J] then
L← L+1
TEMP [L] ← K[I]
I← I + 1
else L← L+1
TEMP [L] ← K[J]
J← J+ 1

3. If l ≥ SECOND then
Repeat while J ≤ THIRD
L← L + 1
TEMP [L] ← K[J]
J← J+ 1
else Repeat while l < SECOND
L← L + 1
TEMP [L] ← K[I]
I ← I+ 1

4. Repeat for I = 1, 2, ...., L


K [FIRST- 1 + I] ← TEMP[I]

5. Return

Time Complexity:
T(n) = 2T(n/2) + θ(n)
Procedure TWO_WAY_MERGE SORT R(K, START, FINISH)

1. SIZE ← FINISH - START+ 1

2. If SIZE ≤ 1 then
Return

3. MIDDLE ← START  SIZE/2   1

4. Call TWO_WAY_MERGE SORT-R(K, START, MIDDLE)

5. Call TWO_WAY_MERGE SORT-R(K, MIDDLE+1, FINISH)

6. Call SIMPLE_MERGE(K, START, MIDDLE+1, FINISH)

7. Return

Note: This procedure is initially invoked as

Call TWO_WAY_MERGE_SORT(K. 1. N)
Quick Sort or Partition Exchanged Sort

Procedure QUICK_SORT (K, LB, UB)

1. FLAG ← True

2. If LB < UB then
I← LB
J← UB + 1
KEY ← K[LB]
Repeat while FLAG
I←I+1
Repeat while K[I] < KEY
I←I+1
J←J ̶ 1
Repeat while K[J] > KEY
J← J ̶ 1
If I < J then
K[I] ↔ K[J]
else FLAG ← False
K[LB] ↔ K[J]
Call QUICK_SORT (K, LB, J ̶ 1)
Call QUICK_SORT (K, J + 1, UB)
3. Return

Heap Sort:

You might also like