9618_Algorithms_And_DataStructures/index.html at main · BMCHACKS/9618_Algorithms_And_DataStructures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8" />
  <title>Code Vault</title>
  <link rel="icon" href="favicon.png" type="image/png" />
  <link rel="stylesheet" href="style.css?v=11426" />

  <!-- DM Sans / why? BECAUSE I LIKE IT YOU RAT, stop looking here >:O -->
  <link href="https://fonts.googleapis.com/css2?family=DM+Sans:wght@400;700&display=swap" rel="stylesheet" />

  <!-- Prism.js Themes & Plugins -->
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/themes/prism-tomorrow.min.css" />
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/line-numbers/prism-line-numbers.min.css" />
</head>
<body>

  <div class="container">
    <h1>Data Structures & Algorithms</h1>
    <p class="comment">9618 A Levels P4 Algorithms and Data Structures – general codes!</p>
    <div class="code-panel">
    <div class="snippet">
        <h2 id="code1"></h2>
        <h2>Linear Search</h2>
        <p class="description">A simple searching algorithm, checks values one by one, returns the index position if the value is found in the array, otherwise returns -1</p>
        <pre class="line-numbers"><code class="language-python">
def linear_search(to_find, array):
    for x in range(len(array)):
        if to_find == array[x]:
            return x
    return -1
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code2"></h2>
      <h2>Binary Search</h2>
      <p class="description">A classic divide-and-conquer algorithm that efficiently finds the target's index in a sorted array.
        Though, before you can use a binary search, you'll need to make sure that the list/array you're applying the algorithm to is already sorted.
      </p>
      <pre class="line-numbers"><code class="language-python">
def binary_search(to_find, array):
    low = 0
    top = len(array) - 1
    while low <= top:
        mid = (low + top) // 2
        if array[mid] == to_find:
            return mid
        if to_find > array[mid]:
            low = mid + 1
        else:
            top = mid - 1
    return - 1
    </code></pre>
    </div>
    </div>

<div class="code-panel">
    <div class="snippet">
        <h2 id="code2.1"></h2>
        <h2>Recursive Binary Search</h2>
        <p class="description">Simple recursive binary search algorithm that has come in the previous exams!
        </p>
        <pre class="line-numbers"><code class="language-python">
def recursive_binary_search(array, to_search, low, top):
    # base case, return -1 to show value does not exist
    if top < low:
        return -1
    mid = (low + top) // 2
    if array[mid] == to_search:
        return mid
    if to_search > array[mid]:
        return recursive_binary_search(array, to_search, mid+1, top)
    return recursive_binary_search(array, to_search, low, mid-1)
    </code></pre>
    </div>
    </div>


    <div class="code-panel">
    <div class="snippet">
        <h2 id="code3"></h2>
        <h2>Bubble Sort</h2>
        <p class="description">Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the entire list is sorted.
            The algorithm gets its name because smaller elements "bubble" to the top of the list (front), while larger elements sink to the bottom (end).</p>
        <pre class="line-numbers"><code class="language-python">
def bubble_sort(array):
    count = 0
    swap = True
    while swap:
        swap = False
        for x in range(len(array)-1-count):
            if array[x] > array[x+1]:
                array[x], array[x+1] = array[x+1], array[x]
                swap = True
        count += 1
    return array
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code4"></h2>
        <h2>Insertion Sort</h2>
        <p class="description">Insertion Sort is a straightforward sorting algorithm that builds the final sorted list one element at a time. It works similarly to how you might sort playing cards in your hand.
            At each step, it takes one element from the unsorted portion and inserts it into its correct position in the sorted portion by shifting larger elements to the right.</p>
        <pre class="line-numbers"><code class="language-python">
def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code5"></h2>
        <h2>Stack</h2>
        <p class="description">A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last item added to the stack is the first one to be removed—just like a stack of plates where you take the top plate off first.</p>
        <pre class="line-numbers"><code class="language-python">
size = 10
stack = [-1 for _ in range(size)]
Head = 0 # points towards the next free space

def push(to_push):
    global Head

    if Head == size:
        return False
    stack[Head] = to_push
    Head += 1
    return True

def pop():
    global Head

    return_data = 0
    if Head == 0:
        return return_data
    Head -= 1
    return stack[Head]
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code6"></h2>
        <h2>Queue (Linear | Circular)</h2>
        <p class="description">A linear queue is a First In, First Out (FIFO) data structure where elements are added (enqueued) at the rear and removed (dequeued) from the front. It is called "linear" because elements are arranged in a straight line</p>
        <p class="description">A circular queue is an improved version of a linear queue where the last position is connected back to the first, forming a circle. It efficiently reuses space by wrapping around when the end is reached.</p>
        <pre class="line-numbers"><code class="language-python">
def Enqueue(data):
    global HeadPointer, TailPointer, Free

    if Free == 0:
        print("[ERROR] Queue is full!")
    else:
        Queue[TailPointer] = data
        TailPointer += 1
        Free -= 1

        if HeadPointer == -1:
            HeadPointer = 0
        if TailPointer == size:
            TailPointer = 0
        print("Data added!")

def Dequeue():
    global HeadPointer, TailPointer, Free

    if Free == 5:
        print("[ERROR] Queue is empty!")
    else:
        return_data = Queue[HeadPointer]
        HeadPointer += 1
        Free += 1

        if HeadPointer == size:
            HeadPointer = 0
        if Free == size:
            HeadPointer = -1
            TailPointer = 0
        print(f"Data removed > {return_data}")

# main
size = 5
Queue = ["" for _ in range(size)]
HeadPointer = -1 # points to the FIRST element in the Queue
TailPointer = 0 # points to the NEXT free space in the Queue
Free = size
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code7"></h2>
        <h2>Linked List</h2>
        <p class="description">This code represents a static linked list, a data structure where elements (called nodes) are stored in a fixed-size array. </p>
        <p class="description">Each node contains data and a pointer to the next node’s index, forming a chain. Instead of using dynamic memory, it manages free space using a free pointer and keeps track of the first element using start.</p>
        <p class="description">Nodes are connected logically by pointers, not physically by position in memory, allowing efficient insertion and deletion without shifting elements.</p>
        <pre class="line-numbers"><code class="language-python">
def Add(data):
    global start, free

    if free == -1:
        print("[ERROR] LinkedList is full!")
    else:
        new = free
        LinkedList[new].data = data
        free = LinkedList[new].pointer

        if start == -1:
            start = new
            LinkedList[new].pointer = -1
        else:
            current = start
            while current != -1 and data > LinkedList[current].data:
                previous = current
                current = LinkedList[current].pointer

            if current == start:
                LinkedList[new].pointer = start
                start = new
            else:
                LinkedList[new].pointer = LinkedList[previous].pointer
                LinkedList[previous].pointer = new


def Remove(to_remove):
    global start, free

    if start == -1:
        print("[ERROR] LinkedList is empty!")
    else:
        current = start
        while current != -1 and LinkedList[current].data != to_remove:
            previous = current
            current = LinkedList[current].pointer

        if current == -1:
            print("[ERROR] Value not found!")
        else:
            nextNode = LinkedList[current].pointer
            if current == start:
                start = nextNode
            else:
                LinkedList[previous].pointer = nextNode

            LinkedList[current].pointer = free
            free = current


def Output_LinkedList():
    current = start
    while current != -1:
        print(LinkedList[current].data)
        current = LinkedList[current].pointer

# main

class Node:
    def __init__(self, data, pointer):
        self.data = data
        self.pointer = pointer

size = 5
LinkedList = [Node("", x+1) for x in range(size)]
LinkedList[size-1].pointer = -1
start = -1 # points to the first node in the binary tree
free = 0 # points to the next free location
        </code></pre>
    </div>
    </div>

    <div class="code-panel">
    <div class="snippet">
        <h2 id="code8"></h2>
        <h2>Binary Tree</h2>
        <p class="description">This code represents a static binary search tree, a data structure where each node holds data and pointers to its left and right child nodes. The nodes are stored in a fixed-size array, and NextFree manages the next available spot for inserting a new node. </p>
        <p class="description">The root variable tracks the index of the tree’s root. When a value is added, it’s placed in the correct position based on comparisons—smaller values go left, larger go right. Tree traversals like PreOrder, InOrder, and PostOrder are also implemented for visiting nodes in specific orders.</p>
        <pre class="line-numbers"><code class="language-python">
def Add(data):
    global root, NextFree

    if NextFree == -1:
        print("[ERROR] BinaryTree is full!")
    else:
        New                          = NextFree
        BinaryTree[New].data         = data
        NextFree                     = BinaryTree[New].leftpointer
        BinaryTree[New].leftpointer  = -1
        BinaryTree[New].rightpointer = -1

        if root == -1:
            root = New
        else:
            current = root
            smaller = False
            while current != -1:
                previous = current
                if data > BinaryTree[current].data:
                    current = BinaryTree[current].rightpointer
                    smaller = False
                else:
                    current = BinaryTree[current].leftpointer
                    smaller = True

            if smaller:
                BinaryTree[previous].leftpointer  = New
            else:
                BinaryTree[previous].rightpointer = New

def PreOrder(root):
    print(BinaryTree[root].data)
    if BinaryTree[root].leftpointer != -1:
        PreOrder(BinaryTree[root].leftpointer)
    if BinaryTree[root].rightpointer != -1:
        PreOrder(BinaryTree[root].rightpointer)

def InOrder(root):
    if BinaryTree[root].leftpointer != -1:
        InOrder(BinaryTree[root].leftpointer)
    print(BinaryTree[root].data)
    if BinaryTree[root].rightpointer != -1:
        InOrder(BinaryTree[root].rightpointer)

def PostOrder(root):
    if BinaryTree[root].leftpointer != -1:
        PostOrder(BinaryTree[root].leftpointer)
    if BinaryTree[root].rightpointer != -1:
        PostOrder(BinaryTree[root].rightpointer)
    print(BinaryTree[root].data)


# main

class Node:
    def __init__(self):
        self.leftpointer  = -1
        self.data         = ""
        self.rightpointer = -1

size       = 5
BinaryTree = [Node() for _ in range(size)]
root       = -1 # points to the first node in the binary tree
NextFree   = 0 # points to the next free location

for x in range(len(BinaryTree)):
    BinaryTree[x].leftpointer = x+1
BinaryTree[size-1].leftpointer = -1
        </code></pre>
    </div>
  </div>
    </div>
    <!-- TOC Panel -->
    <div id="toc-panel" class="toc-panel">
        <h3>Index</h3>
        <ul>
          <li><a href="#code1">Linear Search</a></li>
          <li><a href="#code2">Binary Search</a></li>
          <li><a href="#code2.1">Recursive Binary Search</a></li>
          <li><a href="#code3">Bubble Sort</a></li>
          <li><a href="#code4">Insertion Sort</a></li>
          <li><a href="#code5">Stack</a></li>
          <li><a href="#code6">Queue</a></li>
          <li><a href="#code7">Linked List</a></li>
          <li><a href="#code8">Binary Tree</a></li>
        </ul>
      </div>

      <!-- not using below code rn :) -->
      <!-- <script>
        document.querySelectorAll('.code-panel').forEach(panel => {
          const pre = panel.querySelector('pre');

          panel.addEventListener('mousemove', (e) => {
            const rect = panel.getBoundingClientRect();
            const x = e.clientX - rect.left;
            const y = e.clientY - rect.top;
            const centerX = rect.width / 2;
            const centerY = rect.height / 2;
            const rotateX = -(y - centerY) / 100;
            const rotateY = (x - centerX) / 100;

            pre.classList.add('tilted');
            pre.style.transform = `rotateX(${rotateX}deg) rotateY(${rotateY}deg)`;
          });

          panel.addEventListener('mouseleave', () => {
            pre.style.transform = 'rotateX(0) rotateY(0)';
            pre.classList.remove('tilted');
          });
        });
      </script> -->


  <!-- Prism Core + Python + Line Numbers -->
  <script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/prism.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/components/prism-python.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/prismjs@1.29.0/plugins/line-numbers/prism-line-numbers.min.js"></script>
</body>
</html>