KEMBAR78
12.1 SortingAlgorithms | PDF | Intellectual Property Law | Copyright Law
Scribd
Upload
11 views3 pages

12.1 SortingAlgorithms

The document describes several algorithms for sorting a list of numbers: bubble sort, selection sort, insertion sort, bucket sort, merge sort, quick sort, and heap sort. Code implementations are provided for each sorting algorithm, demonstrating how to sort a sample list called cList using each approach. The document is a reference for different sorting algorithms and includes code examples to implement the various sorting methods on a list.

Uploaded by

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

12.1 SortingAlgorithms

The document describes several algorithms for sorting a list of numbers: bubble sort, selection sort, insertion sort, bucket sort, merge sort, quick sort, and heap sort. Code implementations are provided for each sorting algorithm, demonstrating how to sort a sample list called cList using each approach. The document is a reference for different sorting algorithms and includes code examples to implement the various sorting methods on a list.

Uploaded by

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

# Created by Elshad Karimov

# Copyright © 2021 AppMillers. All rights reserved.

import math

def bubbleSort(customList):
for i in range(len(customList)-1):
for j in range(len(customList)-i-1):
if customList[j] > customList[j+1]:
customList[j], customList[j+1] = customList[j+1], customList[j]
print(customList)

def selectionSort(customList):
for i in range(len(customList)):
min_index = i
for j in range(i+1, len(customList)):
if customList[min_index] > customList[j]:
min_index = j
customList[i], customList[min_index] = customList[min_index], customList[i]
print(customList)

def insertionSort(customList):
for i in range(1, len(customList)):
key = customList[i]
j = i-1
while j>=0 and key < customList[j]:
customList[j+1] = customList[j]
j -= 1
customList[j+1] = key
return customList

def bucketSort(customList):
numberofBuckets = round(math.sqrt(len(customList)))
maxValue = max(customList)
arr = []

for i in range(numberofBuckets):
arr.append([])
for j in customList:
index_b = math.ceil(j*numberofBuckets/maxValue)
arr[index_b-1].append(j)

for i in range(numberofBuckets):
arr[i] = insertionSort(arr[i])

k = 0
for i in range(numberofBuckets):
for j in range(len(arr[i])):
customList[k] = arr[i][j]
k += 1
return customList

def merge(customList, l, m, r):


n1 = m - l + 1
n2 = r - m

L = [0] * (n1)
R = [0] * (n2)

for i in range(0, n1):


L[i] = customList[l+i]

for j in range(0, n2):


R[j] = customList[m+1+j]

i = 0
j = 0
k = l
while i < n1 and j < n2:
if L[i] <= R[j]:
customList[k] = L[i]
i += 1
else:
customList[k] = R[j]
j += 1
k += 1
while i < n1:
customList[k] = L[i]
i += 1
k += 1

while j < n2:


customList[k] = R[j]
j += 1
k += 1

def mergeSort(customList, l, r):


if l < r:
m = (l+(r-1))//2
mergeSort(customList, l, m)
mergeSort(customList, m+1, r)
merge(customList, l, m, r)
return customList

def partition(customList, low, high):


i = low - 1
pivot = customList[high]
for j in range(low,high):
if customList[j] <= pivot:
i += 1
customList[i], customList[j] = customList[j], customList[i]
customList[i+1], customList[high] = customList[high], customList[i+1]
return (i+1)

def quickSort(customList, low, high):


if low < high:
pi = partition(customList, low, high)
quickSort(customList, low, pi-1)
quickSort(customList, pi+1, high)

def heapify(customList, n, i):


smallest = i
l = 2*i + 1
r = 2*i + 2
if l < n and customList[l] < customList[smallest]:
smallest = l

if r < n and customList[r] < customList[smallest]:


smallest = r

if smallest != i:
customList[i], customList[smallest] = customList[smallest], customList[i]
heapify(customList, n, smallest)

def heapSort(customList):
n = len(customList)
for i in range(int(n/2)-1, -1, -1):
heapify(customList, n, i)

for i in range(n-1,0,-1):
customList[i], customList[0] = customList[0], customList[i]
heapify(customList, i, 0)
# customList.reverse()

cList = [2,1,7,6,5,3,4,9,8]
heapSort(cList)
print(cList)

You might also like