Last active
April 21, 2023 17:38
-
-
Save myQwil/a26f851fef8b59d5c19ee86e43d22dfb to your computer and use it in GitHub Desktop.
Visual representation of the quicksort algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import sys, random, time | |
| class qlist(list): | |
| def genseed(self): | |
| self.seed = random.randrange(sys.maxsize) | |
| def __init__(self, iterable): | |
| super().__init__(iterable) | |
| self.vis = len(self) <= 16 | |
| self.genseed() | |
| def __str__(self): | |
| return '[' + ' '.join(map(str, self)) + ']' | |
| def __vis(self, i, j, m, n): | |
| s = ''.join([' ' + ' ' * len('%i' % self[x]) for x in range(m)]) + '|' | |
| s += ' '.join([('_' if x == i or x == j else ' ') * len('%i' % self[x]) \ | |
| for x in range(m, n)]) + '|' | |
| print(f'\n{s}\n{self}') | |
| def __sort_bubble(self): | |
| print('\nBubble Sort') | |
| n = len(self) | |
| self.ncomps = n * (n - 1) // 2 | |
| for i in range(n - 1, 0, -1): | |
| for j in range(i): | |
| k = j + 1 | |
| if self[j] > self[k]: | |
| self[j], self[k] = self[k], self[j] ; self.nswaps += 1 | |
| self.vis and self.__vis(j, k, j, i + 1) | |
| def __sort_selection(self): | |
| print('\nSelection Sort') | |
| n = len(self) | |
| self.nswaps = n - 1 | |
| self.ncomps = n * (n - 1) // 2 | |
| for i in range(n - 1): | |
| m = i | |
| for j in range(i + 1, n): | |
| if self[m] > self[j]: | |
| m = j | |
| self[i], self[m] = self[m], self[i] | |
| self.vis and self.__vis(i, m, i, n) | |
| def __sort_insertion(self): | |
| print('\nInsertion Sort') | |
| for i in range(1, len(self)): | |
| key = self[i] | |
| j = i - 1 | |
| while j >= 0 and key < self[j]: | |
| self[j + 1] = self[j] | |
| j -= 1 | |
| self.ncomps += i - j | |
| self[j + 1] = key | |
| self.vis and self.__vis(j + 1, j + 1, j + 1, i + 1) | |
| self.nswaps = self.ncomps // 3 | |
| def __sort_quick(self, lo, hi): | |
| while lo < hi: | |
| # rand = random.randrange(lo, hi) | |
| # self.__swap(lo, rand, lo, hi + 1) | |
| pivot = self[lo] | |
| i, j = lo + 1, hi | |
| while True: | |
| while self[j] > pivot: | |
| j -= 1 | |
| while self[i] < pivot and i < j: | |
| i += 1 | |
| if i >= j: | |
| if j != lo: | |
| self[lo], self[j] = self[j], self[lo] ; self.nswaps += 1 | |
| self.vis and self.__vis(lo, j, lo, hi + 1) | |
| self.ncomps += (i - (lo + 1)) + (hi - j) + 2 | |
| break | |
| self[i], self[j] = self[j], self[i] ; self.nswaps += 1 | |
| self.vis and self.__vis(i, j, lo, hi + 1) | |
| i += 1 ; j -= 1 | |
| if j - lo < hi - j: | |
| self.__sort_quick(lo, j - 1) | |
| lo = j + 1 | |
| else: | |
| self.__sort_quick(j + 1, hi) | |
| hi = j - 1 | |
| def shuffle(self): | |
| random.seed(self.seed) | |
| random.shuffle(self) | |
| return self | |
| def sort(self, t=None): | |
| self.nswaps, self.ncomps = 0, 0 | |
| timer = time.time() | |
| self.vis and print(f'\n{self}') | |
| if t == 'b': self.__sort_bubble() | |
| elif t == 's': self.__sort_selection() | |
| elif t == 'i': self.__sort_insertion() | |
| else: | |
| print('\nQuick Sort') | |
| self.__sort_quick(0, len(self) - 1) | |
| timer = time.time() - timer | |
| print(f'Swaps: {self.nswaps}\nComparisons: {self.ncomps}\nTime: {timer}' | |
| + f'\nSeed: {self.seed}') | |
| passed = True | |
| for i in range(len(self) - 1): | |
| if self[i] > self[i + 1]: | |
| passed = False | |
| break | |
| print(f'Sorting {"passed" if passed else "failed"}') | |
| data = qlist( [i for i in range(0, 2048)] ) | |
| data.shuffle().sort() | |
| data.shuffle().sort('i') | |
| data.shuffle().sort('s') | |
| data.shuffle().sort('b') | |
| data.genseed() | |
| data.shuffle().sort() | |
| data.shuffle().sort('i') | |
| data.shuffle().sort('s') | |
| data.shuffle().sort('b') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment