Average and worst case time complexity: n^2
Best case time complexity: n when array is already sorted.
Worst case: when the array is reverse sorted.
Best, average and worst case time complexity: n^2 which is independent of distribution of data.
Best, average and worst case time complexity:
Best, average and worst case time complexity:
GFG
It is a divide and conquer approach with recurrence relation:
when the array is sorted or reverse sorted, the partition algorithm divides the array in two subarrays with 0 and n-1 elements. Therefore,
On an average, the partition algorithm divides the array in two subarrays with equal size. Therefore,
def partition(array, low, high):
# Choose the rightmost element as pivot
pivot = array[high]
# Pointer for greater element
i = low - 1
# Traverse through all elements
# compare each element with pivot
for j in range(low, high):
if array[j] <= pivot:
# If element smaller than pivot is found
# swap it with the greater element pointed by i
i = i + 1
# Swapping element at i with element at j
(array[i], array[j]) = (array[j], array[i])
# Swap the pivot element with
# the greater element specified by i
(array[i + 1], array[high]) = (array[high], array[i + 1])
# Return the position from where partition is done
return i + 1
# Function to perform quicksort
def quicksort(array, low, high):
if low < high:
# Find pivot element such that
# element smaller than pivot are on the left
# element greater than pivot are on the right
pi = partition(array, low, high)
# Recursive call on the left of pivot
quicksort(array, low, pi - 1)
# Recursive call on the right of pivot
quicksort(array, pi + 1, high)
# Driver code
if __name__ == '__main__':
array = [10, 7, 8, 9, 1, 5]
N = len(array)
# Function call
quicksort(array, 0, N - 1)
print('Sorted array:')
for x in array:
print(x, end=" ")
The Ford Johnson sort is a sorting algorithm that is suitable for sorting strings in lexicographical order. It works by splitting the strings into characters and then comparing character by character.
The basic algorithm is as follows:
Here is an example:
Input: ["dog", "cat", "bird"]
1) Split into characters and add delimiter:
d$
o$
g$
c$
a$
t$
b$
i$
r$
d$
2) Sort:
a$
b$
c$
d$
d$
g$
i$
o$
r$
t$
3) Remove delimiters:
a
b
c
d
d
g
i
o
r
t
4) Reassemble strings:
["a", "b", "c", "dog", "i", "o", "r", "t"]
The time complexity of the Ford Johnson sort is O(n log n) where n is the total number of characters in all strings, due to the underlying sorting algorithm used. The space complexity is O(n) due to needing to store the individual characters.
The advantage of this algorithm is that it can efficiently sort strings of variable length. However, it requires more space than an in-place string sort.