[{"_1":2,"_171":-5,"_172":-5},"loaderData",{"_3":4,"_91":92},"root",{"_5":6,"_34":35,"_64":65},"ctx",{"_7":8,"_23":-5,"_24":25,"_26":27,"_28":20,"_29":20,"_30":20,"_31":32,"_33":20},"auth",{"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20,"_21":22},"sessionClaims","sessionId","sessionStatus","userId","actor","orgId","orgRole","orgSlug","orgPermissions","factorVerificationAge","isAuthenticated",false,"tokenType","session_token","user","preferencesKeybindings","default","preferencesTheme","light","preferencesFixers","preferencesCopilot","preferencesSelectionAi","notificationCount",0,"flagDenols","ENV",{"_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},"REACT_APP_SENTRY_DSN","https://586020d86f05489db63a554690acf1e9@o1398359.ingest.sentry.io/6724499","VAL_RUNTIME_NAME","prod","RENDER_GIT_COMMIT","7037b4412b49b7328160fa57e59f17dfe8779fc7","RENDER_GIT_BRANCH","main","CLERK_PUBLISHABLE_KEY","pk_live_Y2xlcmsudmFsLnRvd24k","POSTHOG_API_TOKEN","phc_nmoyuAkStEZuUp69rYlg1DZgrIt19Gx0Y4Hwf8tGgJP","POSTHOG_API_HOST","https://wart.val.town","WEB_API_TEMPLATE","https://{val}.web.val.run","APP_URL","https://www.val.town","MODULE_URL","https://esm.town","VANITY_WEB_API_TEMPLATE","https://{label}.val.run/","DENOLS_URL","https://lsp.val.town","NODE_ENV","production","API_URL","https://api.val.town","clerkState",{"_66":67},"__internal_clerk_state",{"_68":69,"_70":45,"_71":72,"_73":72,"_74":20,"_75":72,"_76":72,"_77":72,"_78":72,"_79":80,"_89":20,"_90":20},"__clerk_ssr_state",{"_21":22,"_9":-5,"_10":-5,"_11":-5,"_12":-5,"_13":-5,"_14":-5,"_15":-5,"_16":-5,"_17":-5,"_18":-5,"_19":20},"__publishableKey","__proxyUrl","","__domain","__isSatellite","__signInUrl","__signUpUrl","__afterSignInUrl","__afterSignUpUrl","__clerk_debug",{"_81":20,"_19":20,"_82":72,"_83":84,"_85":72,"_86":45,"_87":20,"_88":72},"isSignedIn","proxyUrl","reason","session-token-and-uat-missing","message","publishableKey","isSatellite","domain","__telemetryDisabled","__telemetryDebug","routes/embed.x.$handle.$name.$",{"_93":94,"_95":96,"_97":98,"_99":100,"_146":147,"_168":169,"_170":-5},"handle","moizedits","name","my-first-val","path","shared/algorithms.ts","project",{"_101":102,"_95":96,"_103":104,"_105":-5,"_106":20,"_107":108,"_109":-5,"_110":-5,"_12":111,"_112":-5,"_113":20,"_114":-5,"_115":32,"_14":116,"_117":118,"_119":118,"_120":121,"_122":121,"_123":121,"_124":118,"_125":118,"_23":126,"_129":130,"_132":133,"_145":20},"id","81453866-3681-11f0-80c0-9e149126039e","createdAt",["D",1747859029594],"deletedAt","legacyEnvVars","privacy","public","description","imageUrl","6acd35c0-3681-11f0-aa91-c30dad1a6213","pinnedFileId","pinPreview","screenshotVersion","likeCount","c6597761-ab04-4b5a-86ef-49722a4c597e","userPerm","r","valPerm","blobPerm","rw","emailPerm","sqlitePerm","projectPerm","telemetryPerm",{"_93":94,"_127":128},"profileImageUrl","https://img.clerk.com/eyJ0eXBlIjoiZGVmYXVsdCIsImlpZCI6Imluc18yTm10cGhQUklwU0tqZHNiOHNnNGd2ZjJURFUiLCJyaWQiOiJ1c2VyXzJ4UThWT25tU2hOdnJkUWdpWUJFTVVvdTVWZyJ9","org",{"_93":94,"_131":128,"_12":111},"avatar","branch",{"_134":135,"_95":43,"_101":136,"_137":102,"_138":-5,"_139":-5,"_140":-5,"_141":-5,"_142":-5,"_143":96,"_144":94},"version",19,"814582d0-3681-11f0-80c0-9e149126039e","projectId","forkedBranchId","forkedBranchVersion","forkedProjectPrivacy","forkedProjectId","forkedProjectOrgId","projectName","userHandle","isOwned","file",{"_101":148,"_95":149,"_150":151,"_152":153,"_154":136,"_155":156,"_157":158,"_103":159,"_134":32,"_160":161,"_162":163,"_164":20,"_165":-5,"_97":166},"0cca2356-3682-11f0-8453-9e149126039e","algorithms.ts","fileId","0cca245a-3682-11f0-8453-9e149126039e","parentId","3cc1f4d3-2dce-494a-9a1c-4d5c13c6ecda","branchId","branchVersion",8,"latest",true,["D",1747859263665],"fileType","script","content","import { Algorithm, AlgorithmStep } from './types';\n\n// Algorithm definitions\nexport const algorithms: Algorithm[] = [\n {\n id: 'bubble-sort',\n name: 'Bubble Sort',\n type: 'sorting',\n description: 'A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.',\n timeComplexity: {\n best: 'O(n)',\n average: 'O(n²)',\n worst: 'O(n²)',\n },\n spaceComplexity: 'O(1)',\n pseudocode: [\n 'procedure bubbleSort(A: list of sortable items)',\n ' n := length(A)',\n ' repeat',\n ' swapped := false',\n ' for i := 1 to n-1 inclusive do',\n ' if A[i-1] > A[i] then',\n ' swap(A[i-1], A[i])',\n ' swapped := true',\n ' end if',\n ' end for',\n ' n := n - 1',\n ' until not swapped',\n 'end procedure',\n ],\n },\n {\n id: 'insertion-sort',\n name: 'Insertion Sort',\n type: 'sorting',\n description: 'A simple sorting algorithm that builds the final sorted array one item at a time. It is efficient for small data sets.',\n timeComplexity: {\n best: 'O(n)',\n average: 'O(n²)',\n worst: 'O(n²)',\n },\n spaceComplexity: 'O(1)',\n pseudocode: [\n 'procedure insertionSort(A: list of sortable items)',\n ' n := length(A)',\n ' for i := 1 to n-1 inclusive do',\n ' j := i',\n ' while j > 0 and A[j-1] > A[j] do',\n ' swap(A[j], A[j-1])',\n ' j := j - 1',\n ' end while',\n ' end for',\n 'end procedure',\n ],\n },\n {\n id: 'selection-sort',\n name: 'Selection Sort',\n type: 'sorting',\n description: 'A simple sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly selects the smallest element from the unsorted sublist and moves it to the end of the sorted sublist.',\n timeComplexity: {\n best: 'O(n²)',\n average: 'O(n²)',\n worst: 'O(n²)',\n },\n spaceComplexity: 'O(1)',\n pseudocode: [\n 'procedure selectionSort(A: list of sortable items)',\n ' n := length(A)',\n ' for i := 0 to n-1 inclusive do',\n ' minIndex := i',\n ' for j := i+1 to n-1 inclusive do',\n ' if A[j] < A[minIndex] then',\n ' minIndex := j',\n ' end if',\n ' end for',\n ' if minIndex ≠ i then',\n ' swap(A[i], A[minIndex])',\n ' end if',\n ' end for',\n 'end procedure',\n ],\n },\n {\n id: 'merge-sort',\n name: 'Merge Sort',\n type: 'sorting',\n description: 'An efficient, stable, comparison-based, divide and conquer sorting algorithm. It divides the input array into two halves, recursively sorts them, and then merges the sorted halves.',\n timeComplexity: {\n best: 'O(n log n)',\n average: 'O(n log n)',\n worst: 'O(n log n)',\n },\n spaceComplexity: 'O(n)',\n pseudocode: [\n 'procedure mergeSort(A: list of sortable items, lo, hi)',\n ' if lo < hi then',\n ' mid := floor((lo + hi) / 2)',\n ' mergeSort(A, lo, mid)',\n ' mergeSort(A, mid + 1, hi)',\n ' merge(A, lo, mid, hi)',\n ' end if',\n 'end procedure',\n '',\n 'procedure merge(A: list of sortable items, lo, mid, hi)',\n ' create temporary arrays L and R',\n ' copy A[lo..mid] to L and A[mid+1..hi] to R',\n ' i := 0, j := 0, k := lo',\n ' while i < length(L) and j < length(R) do',\n ' if L[i] <= R[j] then',\n ' A[k] := L[i]',\n ' i := i + 1',\n ' else',\n ' A[k] := R[j]',\n ' j := j + 1',\n ' end if',\n ' k := k + 1',\n ' end while',\n ' copy remaining elements of L and R back to A',\n 'end procedure',\n ],\n },\n {\n id: 'quick-sort',\n name: 'Quick Sort',\n type: 'sorting',\n description: 'An efficient, in-place sorting algorithm that uses a divide-and-conquer strategy. It picks an element as a pivot and partitions the array around the pivot.',\n timeComplexity: {\n best: 'O(n log n)',\n average: 'O(n log n)',\n worst: 'O(n²)',\n },\n spaceComplexity: 'O(log n)',\n pseudocode: [\n 'procedure quickSort(A: list of sortable items, lo, hi)',\n ' if lo < hi then',\n ' p := partition(A, lo, hi)',\n ' quickSort(A, lo, p - 1)',\n ' quickSort(A, p + 1, hi)',\n ' end if',\n 'end procedure',\n '',\n 'procedure partition(A: list of sortable items, lo, hi)',\n ' pivot := A[hi]',\n ' i := lo - 1',\n ' for j := lo to hi - 1 do',\n ' if A[j] <= pivot then',\n ' i := i + 1',\n ' swap(A[i], A[j])',\n ' end if',\n ' end for',\n ' swap(A[i + 1], A[hi])',\n ' return i + 1',\n 'end procedure',\n ],\n },\n {\n id: 'binary-search',\n name: 'Binary Search',\n type: 'searching',\n description: 'An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you\\'ve narrowed down the possible locations to just one.',\n timeComplexity: {\n best: 'O(1)',\n average: 'O(log n)',\n worst: 'O(log n)',\n },\n spaceComplexity: 'O(1)',\n pseudocode: [\n 'procedure binarySearch(A: sorted list of items, target)',\n ' lo := 0',\n ' hi := length(A) - 1',\n ' while lo <= hi do',\n ' mid := floor((lo + hi) / 2)',\n ' if A[mid] < target then',\n ' lo := mid + 1',\n ' else if A[mid] > target then',\n ' hi := mid - 1',\n ' else',\n ' return mid',\n ' end if',\n ' end while',\n ' return -1 // Not found',\n 'end procedure',\n ],\n },\n {\n id: 'linear-search',\n name: 'Linear Search',\n type: 'searching',\n description: 'A simple search algorithm that checks each element of the list until a match is found or the whole list has been searched.',\n timeComplexity: {\n best: 'O(1)',\n average: 'O(n)',\n worst: 'O(n)',\n },\n spaceComplexity: 'O(1)',\n pseudocode: [\n 'procedure linearSearch(A: list of items, target)',\n ' for i := 0 to length(A) - 1 do',\n ' if A[i] = target then',\n ' return i',\n ' end if',\n ' end for',\n ' return -1 // Not found',\n 'end procedure',\n ],\n },\n];\n\n// Algorithm implementation functions\nexport function generateBubbleSortSteps(array: number[]): AlgorithmStep[] {\n const steps: AlgorithmStep[] = [];\n const arr = [...array];\n const n = arr.length;\n \n // Initial state\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: [],\n description: 'Initial array'\n });\n \n let swapped;\n let sortedCount = 0;\n \n do {\n swapped = false;\n for (let i = 0; i < n - 1 - sortedCount; i++) {\n // Comparing elements\n steps.push({\n array: [...arr],\n highlightIndices: [i, i + 1],\n sortedIndices: Array.from({ length: sortedCount }, (_, idx) => n - 1 - idx),\n description: `Comparing ${arr[i]} and ${arr[i + 1]}`\n });\n \n if (arr[i] > arr[i + 1]) {\n // Swap elements\n [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];\n swapped = true;\n \n steps.push({\n array: [...arr],\n highlightIndices: [i, i + 1],\n sortedIndices: Array.from({ length: sortedCount }, (_, idx) => n - 1 - idx),\n description: `Swapped ${arr[i + 1]} and ${arr[i]}`\n });\n }\n }\n \n sortedCount++;\n \n // Mark the largest element as sorted\n if (n - sortedCount >= 0) {\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: Array.from({ length: sortedCount }, (_, idx) => n - 1 - idx),\n description: `Element ${arr[n - sortedCount]} is now in its correct position`\n });\n }\n } while (swapped);\n \n // Final state\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: Array.from({ length: n }, (_, idx) => idx),\n description: 'Array is sorted'\n });\n \n return steps;\n}\n\nexport function generateInsertionSortSteps(array: number[]): AlgorithmStep[] {\n const steps: AlgorithmStep[] = [];\n const arr = [...array];\n const n = arr.length;\n \n // Initial state\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: [0],\n description: 'Initial array with first element considered sorted'\n });\n \n for (let i = 1; i < n; i++) {\n // Current element to be inserted\n steps.push({\n array: [...arr],\n highlightIndices: [i],\n sortedIndices: Array.from({ length: i }, (_, idx) => idx),\n description: `Inserting element ${arr[i]} into the sorted portion`\n });\n \n let j = i;\n while (j > 0 && arr[j - 1] > arr[j]) {\n // Compare elements\n steps.push({\n array: [...arr],\n highlightIndices: [j - 1, j],\n sortedIndices: Array.from({ length: i }, (_, idx) => idx !== j && idx !== j - 1 ? idx : -1).filter(idx => idx !== -1),\n description: `Comparing ${arr[j - 1]} and ${arr[j]}`\n });\n \n // Swap elements\n [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];\n \n steps.push({\n array: [...arr],\n highlightIndices: [j - 1, j],\n sortedIndices: Array.from({ length: i }, (_, idx) => idx !== j && idx !== j - 1 ? idx : -1).filter(idx => idx !== -1),\n description: `Swapped ${arr[j]} and ${arr[j - 1]}`\n });\n \n j--;\n }\n \n // Element inserted\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: Array.from({ length: i + 1 }, (_, idx) => idx),\n description: `Element ${arr[j]} inserted into correct position`\n });\n }\n \n // Final state\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: Array.from({ length: n }, (_, idx) => idx),\n description: 'Array is sorted'\n });\n \n return steps;\n}\n\n// Generate steps for binary search\nexport function generateBinarySearchSteps(array: number[], target: number): AlgorithmStep[] {\n const steps: AlgorithmStep[] = [];\n const arr = [...array].sort((a, b) => a - b); // Ensure array is sorted\n let left = 0;\n let right = arr.length - 1;\n \n // Initial state\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: [],\n description: `Searching for ${target} in the sorted array`\n });\n \n while (left <= right) {\n const mid = Math.floor((left + right) / 2);\n \n // Highlight current search range\n steps.push({\n array: [...arr],\n highlightIndices: Array.from({ length: right - left + 1 }, (_, idx) => left + idx),\n sortedIndices: [],\n description: `Searching in the range [${left}, ${right}]`\n });\n \n // Highlight middle element\n steps.push({\n array: [...arr],\n highlightIndices: [mid],\n sortedIndices: [],\n description: `Checking middle element at index ${mid}: ${arr[mid]}`\n });\n \n if (arr[mid] === target) {\n // Found the target\n steps.push({\n array: [...arr],\n highlightIndices: [mid],\n sortedIndices: [],\n description: `Found ${target} at index ${mid}`\n });\n break;\n } else if (arr[mid] < target) {\n // Search in the right half\n left = mid + 1;\n steps.push({\n array: [...arr],\n highlightIndices: Array.from({ length: right - left + 1 }, (_, idx) => left + idx),\n sortedIndices: [],\n description: `${arr[mid]} < ${target}, searching in the right half`\n });\n } else {\n // Search in the left half\n right = mid - 1;\n steps.push({\n array: [...arr],\n highlightIndices: Array.from({ length: right - left + 1 }, (_, idx) => left + idx),\n sortedIndices: [],\n description: `${arr[mid]} > ${target}, searching in the left half`\n });\n }\n }\n \n // If target not found\n if (left > right) {\n steps.push({\n array: [...arr],\n highlightIndices: [],\n sortedIndices: [],\n description: `${target} not found in the array`\n });\n }\n \n return steps;\n}\n\n// Function to generate algorithm steps based on algorithm ID\nexport function generateAlgorithmSteps(algorithmId: string, array: number[], target?: number): AlgorithmStep[] {\n switch (algorithmId) {\n case 'bubble-sort':\n return generateBubbleSortSteps(array);\n case 'insertion-sort':\n return generateInsertionSortSteps(array);\n case 'binary-search':\n return generateBinarySearchSteps(array, target || array[Math.floor(Math.random() * array.length)]);\n // Add other algorithms as needed\n default:\n return [];\n }\n}","deleted","label",[167,149],"shared","permalink","https://www.val.town/x/moizedits/my-first-val/code/shared/algorithms.ts","extension","actionData","errors"]