Forem: Christian

Implementing Selection Sort in Javascript

Christian — Mon, 08 Jul 2024 20:02:00 +0000

Selection sort works by selecting the minimum value in a list and swapping it with the first value in the list. It then starts at the second position, selects the smallest value in the remaining list, and swaps it with the second element. It continues iterating through the list and swapping elements until it reaches the end of the list. Now the list is sorted. Selection sort has quadratic time complexity in all cases.

Instructions: Write a function selectionSort which takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.

Waiting: selectionSort should be a function.
Waiting: selectionSort should return a sorted array (least to greatest).
Waiting: selectionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]) should return an array that is unchanged except for order.
Waiting: selectionSort should not use the built-in .sort() method.

Let's implement the selectionSort function according to the specifications. Here's a step-by-step implementation of the selection sort algorithm:

function selectionSort(array) {
  // Make a copy of the original array to avoid modifying it directly
  let arr = [...array];

  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;

    // Find the index of the minimum element in the unsorted part
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first element of the unsorted part
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

Let's break down this implementation:

We start by creating a copy of the input array using the spread operator ([...array]). This ensures we don't modify the original array.
We use an outer loop that iterates through the array from the first element to the second-to-last element. This represents the boundary between the sorted and unsorted portions of the array.
For each iteration of the outer loop:
- We assume the current element is the minimum and store its index.
- We use an inner loop to scan the rest of the array (the unsorted portion) to find the actual minimum element.
- If we find a smaller element, we update the minIndex.
After finding the minimum element in the unsorted portion, we swap it with the first element of the unsorted portion (if they're not already the same element).
This process continues until the entire array is sorted.
Finally, we return the sorted array.

This implementation satisfies all the given requirements:

It's a function named selectionSort.
It returns a sorted array from least to greatest.
It works correctly for the given example input.
It doesn't use the built-in .sort() method.

You can test it with the provided example:

console.log(selectionSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));

This will output the sorted array:

[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]

Note that while this implementation correctly sorts the array, selection sort has a time complexity of O(n^2) in all cases, making it inefficient for large arrays. However, it has the advantage of making the minimum number of swaps (at most n - 1 swaps, where n is the number of elements), which can be beneficial in certain situations where writing to memory is a costly operation.

Bubble Sort: Given an Array of Unsorted Items, Return A Sorted Array

Christian — Mon, 08 Jul 2024 19:36:38 +0000

While most modern languages have built-in sorting methods for operations like this, it is still important to understand some of the common basic approaches and learn how they can be implemented.

The bubble sort method starts at the beginning of an unsorted array and 'bubbles up' unsorted values towards the end, iterating through the array until it is completely sorted.

It does this by comparing adjacent items and swapping them if they are out of order. The method continues looping through the array until no swaps occur at which point the array is sorted.

This method requires multiple iterations through the array and for average and worst cases has quadratic time complexity. While simple, it is usually impractical in most situations.

Instructions:

Write a function bubbleSort which takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.

Waiting: bubbleSort should be a function.
Waiting: bubbleSort should return a sorted array (least to greatest).
Waiting: bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]) should return an array that is unchanged except for order.
Waiting: bubbleSort should not use the built-in .sort() method.

Let's implement the bubbleSort function according to the specifications. Here's a step-by-step implementation of the bubble sort algorithm:

function bubbleSort(array) {
  // Make a copy of the original array to avoid modifying it directly
  let arr = [...array];
  let swapped;

  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        // Swap elements
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }
  } while (swapped);

  return arr;
}

Let's break down this implementation:

We start by creating a copy of the input array using the spread operator ([...array]). This ensures we don't modify the original array.
We use a do-while loop that continues as long as we make any swaps in a pass through the array.
Inside the loop, we iterate through the array, comparing adjacent elements.
If we find two adjacent elements that are out of order (the left one is greater than the right one), we swap them using destructuring assignment.
We set the swapped flag to true whenever we perform a swap.
The outer loop continues until we make a full pass through the array without any swaps, indicating that the array is fully sorted.
Finally, we return the sorted array.

This implementation satisfies all the given requirements:

It's a function named bubbleSort.
It returns a sorted array from least to greatest.
It works correctly for the given example input.
It doesn't use the built-in .sort() method.

You can test it with the provided example:

console.log(bubbleSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92]));

This will output the sorted array:

[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]

Note that while this implementation correctly sorts the array, bubble sort has a time complexity of O(n^2) in the average and worst cases, making it inefficient for large arrays. However, it's a simple algorithm to understand and implement, which makes it useful for educational purposes.

Automate Github Pull Requests With NodeJS API

Christian — Mon, 08 Jul 2024 19:07:42 +0000

Integrating with the GitHub API using Node.js, TypeScript, and NestJS involves several steps. Here's a detailed guide to achieve this:

1. Set Up a New NestJS Project

First, create a new NestJS project if you don't have one already:

npm i -g @nestjs/cli
nest new github-pr-automation
cd github-pr-automation

2. Install Axios and Other Necessary Dependencies

You need Axios to make HTTP requests:

npm install axios
npm install @nestjs/config
npm install @types/axios --save-dev

3. Configure Environment Variables

Create a .env file in the root of your project and add your GitHub personal access token and other necessary configurations:

GITHUB_TOKEN=your_personal_access_token
GITHUB_OWNER=your_github_username_or_org
GITHUB_REPO=your_repository_name

4. Create a Configuration Module

Set up a configuration module to read environment variables. Update app.module.ts to import the configuration module:

import { Module } from '@nestjs/common';
import { ConfigModule } from '@nestjs/config';
import { GithubModule } from './github/github.module';

@Module({
  imports: [
    ConfigModule.forRoot({
      isGlobal: true,
    }),
    GithubModule,
  ],
})
export class AppModule {}

5. Create the GitHub Module

Generate a GitHub module and service:

nest generate module github
nest generate service github

6. Implement the GitHub Service

In src/github/github.service.ts, implement the service to create a pull request:

import { Injectable, HttpService } from '@nestjs/common';
import { ConfigService } from '@nestjs/config';
import axios from 'axios';

@Injectable()
export class GithubService {
  private readonly githubToken: string;
  private readonly owner: string;
  private readonly repo: string;

  constructor(private configService: ConfigService) {
    this.githubToken = this.configService.get<string>('GITHUB_TOKEN');
    this.owner = this.configService.get<string>('GITHUB_OWNER');
    this.repo = this.configService.get<string>('GITHUB_REPO');
  }

  async createPullRequest(head: string, base: string, title: string, body: string): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls`;

    const data = {
      title,
      head,
      base,
      body,
    };

    const headers = {
      Authorization: `token ${this.githubToken}`,
      Accept: 'application/vnd.github.v3+json',
    };

    try {
      const response = await axios.post(url, data, { headers });
      console.log('Pull request created successfully:', response.data.html_url);
    } catch (error) {
      console.error('Error creating pull request:', error.response ? error.response.data : error.message);
    }
  }
}

7. Create a Controller to Trigger the Pull Request

Generate a GitHub controller:

nest generate controller github

In src/github/github.controller.ts, implement the controller:

import { Controller, Post, Body } from '@nestjs/common';
import { GithubService } from './github.service';

@Controller('github')
export class GithubController {
  constructor(private readonly githubService: GithubService) {}

  @Post('create-pull-request')
  async createPullRequest(
    @Body('head') head: string,
    @Body('base') base: string,
    @Body('title') title: string,
    @Body('body') body: string,
  ): Promise<void> {
    await this.githubService.createPullRequest(head, base, title, body);
  }
}

8. Testing the API

You can test the API using tools like Postman or curl. Start your NestJS application:

npm run start

Send a POST request to http://localhost:3000/github/create-pull-request with the required data:

{
  "head": "feature-branch",
  "base": "main",
  "title": "Automated Pull Request",
  "body": "This is an automated pull request."
}

9. Full Code Structure

Here’s a summary of the code structure:

src/
├── app.module.ts
├── github/
│   ├── github.controller.ts
│   ├── github.module.ts
│   ├── github.service.ts
├── main.ts
.env

`app.module.ts`

import { Module } from '@nestjs/common';
import { ConfigModule } from '@nestjs/config';
import { GithubModule } from './github/github.module';

@Module({
  imports: [
    ConfigModule.forRoot({
      isGlobal: true,
    }),
    GithubModule,
  ],
})
export class AppModule {}

`github.module.ts`

import { Module } from '@nestjs/common';
import { GithubService } from './github.service';
import { GithubController } from './github.controller';

@Module({
  providers: [GithubService],
  controllers: [GithubController],
})
export class GithubModule {}

`github.service.ts`

import { Injectable } from '@nestjs/common';
import { ConfigService } from '@nestjs/config';
import axios from 'axios';

@Injectable()
export class GithubService {
  private readonly githubToken: string;
  private readonly owner: string;
  private readonly repo: string;

  constructor(private configService: ConfigService) {
    this.githubToken = this.configService.get<string>('GITHUB_TOKEN');
    this.owner = this.configService.get<string>('GITHUB_OWNER');
    this.repo = this.configService.get<string>('GITHUB_REPO');
  }

  async createPullRequest(head: string, base: string, title: string, body: string): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls`;

    const data = {
      title,
      head,
      base,
      body,
    };

    const headers = {
      Authorization: `token ${this.githubToken}`,
      Accept: 'application/vnd.github.v3+json',
    };

    try {
      const response = await axios.post(url, data, { headers });
      console.log('Pull request created successfully:', response.data.html_url);
    } catch (error) {
      console.error('Error creating pull request:', error.response ? error.response.data : error.message);
    }
  }
}

`github.controller.ts`

import { Controller, Post, Body } from '@nestjs/common';
import { GithubService } from './github.service';

@Controller('github')
export class GithubController {
  constructor(private readonly githubService: GithubService) {}

  @Post('create-pull-request')
  async createPullRequest(
    @Body('head') head: string,
    @Body('base') base: string,
    @Body('title') title: string,
    @Body('body') body: string,
  ): Promise<void> {
    await this.githubService.createPullRequest(head, base, title, body);
  }
}

With this setup, you can automate pull requests using the GitHub API within a NestJS application written in TypeScript.

Further, here's how you can extend the existing NestJS service to include the following functions in order to make this more comprehensive.

Create Pull Requests
Approve Pull Requests
Close Pull Requests
Comment on Pull Requests
Request Changes on Pull Requests

1. Extending the GitHub Service

Update the GithubService to include methods for each of these actions:

import { Injectable } from '@nestjs/common';
import { ConfigService } from '@nestjs/config';
import axios from 'axios';

@Injectable()
export class GithubService {
  private readonly githubToken: string;
  private readonly owner: string;
  private readonly repo: string;

  constructor(private configService: ConfigService) {
    this.githubToken = this.configService.get<string>('GITHUB_TOKEN');
    this.owner = this.configService.get<string>('GITHUB_OWNER');
    this.repo = this.configService.get<string>('GITHUB_REPO');
  }

  private getHeaders() {
    return {
      Authorization: `token ${this.githubToken}`,
      Accept: 'application/vnd.github.v3+json',
    };
  }

  async createPullRequest(head: string, base: string, title: string, body: string): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls`;

    const data = {
      title,
      head,
      base,
      body,
    };

    try {
      const response = await axios.post(url, data, { headers: this.getHeaders() });
      console.log('Pull request created successfully:', response.data.html_url);
    } catch (error) {
      console.error('Error creating pull request:', error.response ? error.response.data : error.message);
    }
  }

  async approvePullRequest(pullRequestNumber: number): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls/${pullRequestNumber}/reviews`;
    const data = {
      event: 'APPROVE',
    };

    try {
      const response = await axios.post(url, data, { headers: this.getHeaders() });
      console.log('Pull request approved successfully:', response.data);
    } catch (error) {
      console.error('Error approving pull request:', error.response ? error.response.data : error.message);
    }
  }

  async closePullRequest(pullRequestNumber: number): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls/${pullRequestNumber}`;

    const data = {
      state: 'closed',
    };

    try {
      const response = await axios.patch(url, data, { headers: this.getHeaders() });
      console.log('Pull request closed successfully:', response.data);
    } catch (error) {
      console.error('Error closing pull request:', error.response ? error.response.data : error.message);
    }
  }

  async commentOnPullRequest(pullRequestNumber: number, comment: string): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/issues/${pullRequestNumber}/comments`;

    const data = {
      body: comment,
    };

    try {
      const response = await axios.post(url, data, { headers: this.getHeaders() });
      console.log('Comment added successfully:', response.data);
    } catch (error) {
      console.error('Error adding comment:', error.response ? error.response.data : error.message);
    }
  }

  async requestChangesOnPullRequest(pullRequestNumber: number, comment: string): Promise<void> {
    const url = `https://api.github.com/repos/${this.owner}/${this.repo}/pulls/${pullRequestNumber}/reviews`;

    const data = {
      body: comment,
      event: 'REQUEST_CHANGES',
    };

    try {
      const response = await axios.post(url, data, { headers: this.getHeaders() });
      console.log('Requested changes successfully:', response.data);
    } catch (error) {
      console.error('Error requesting changes:', error.response ? error.response.data : error.message);
    }
  }
}

2. Update the GitHub Controller

Extend the controller to handle requests for these new methods:

import { Controller, Post, Body, Param, Patch } from '@nestjs/common';
import { GithubService } from './github.service';

@Controller('github')
export class GithubController {
  constructor(private readonly githubService: GithubService) {}

  @Post('create-pull-request')
  async createPullRequest(
    @Body('head') head: string,
    @Body('base') base: string,
    @Body('title') title: string,
    @Body('body') body: string,
  ): Promise<void> {
    await this.githubService.createPullRequest(head, base, title, body);
  }

  @Post('approve-pull-request/:number')
  async approvePullRequest(@Param('number') pullRequestNumber: number): Promise<void> {
    await this.githubService.approvePullRequest(pullRequestNumber);
  }

  @Patch('close-pull-request/:number')
  async closePullRequest(@Param('number') pullRequestNumber: number): Promise<void> {
    await this.githubService.closePullRequest(pullRequestNumber);
  }

  @Post('comment-pull-request/:number')
  async commentOnPullRequest(
    @Param('number') pullRequestNumber: number,
    @Body('comment') comment: string,
  ): Promise<void> {
    await this.githubService.commentOnPullRequest(pullRequestNumber, comment);
  }

  @Post('request-changes/:number')
  async requestChangesOnPullRequest(
    @Param('number') pullRequestNumber: number,
    @Body('comment') comment: string,
  ): Promise<void> {
    await this.githubService.requestChangesOnPullRequest(pullRequestNumber, comment);
  }
}

3. Testing the API

You can now test the new endpoints using tools like Postman or curl.

Create Pull Request

  POST http://localhost:3000/github/create-pull-request
  {
    "head": "feature-branch",
    "base": "main",
    "title": "Automated Pull Request",
    "body": "This is an automated pull request."
  }

Approve Pull Request

  POST http://localhost:3000/github/approve-pull-request/1

Close Pull Request

  PATCH http://localhost:3000/github/close-pull-request/1

Comment on Pull Request

  POST http://localhost:3000/github/comment-pull-request/1
  {
    "comment": "This is a comment on the pull request."
  }

Request Changes on Pull Request

  POST http://localhost:3000/github/request-changes/1
  {
    "comment": "Please make the following changes..."
  }

With this setup, you can create, approve, close, comment on, and request changes on pull requests using the GitHub API within your NestJS application. What we are missing now are Jest / Vite tests in order to properly build out this system.